# Resources for complexity results for optimization problems in restricted graph classes

I am specifically interested in optimization problems in graphs (minimum coloring, maximum clique, maximum matching etc.) and I need a resource (database) which contains complexity results on different graph classes. The best resource that I know is the following:

http://graphclasses.org/

I think this web site is great because it covers all the graph classes, however the results presented (recognition, independent set, domination) in the site and my interests do not match.

I am looking for similar resources.

Thanks.

• Maximum Clique for G is equivalent to Maximum Independent Set for the complement of G and therefore ISGCI contains necessary information. Maximum Matching is always polynomial-time solvable by Edmonds’s matching algorithm. Dec 12, 2010 at 12:48
• Maybe I am confusing but is it sufficient to have a maximum independent set algorithm for a specific graph class to solve maximum clique problem in the same graph class? I think in order to have this proporty the complement of the graph should also be in the same graph class. Dec 12, 2010 at 12:59
• On the other hand, you are complety right on the maximum matching issue. However there can be exist a more efficient matching algorithm for a specific graph class (e.g. trees, planar graphs, etc.). Dec 12, 2010 at 13:02
• Suppose you want to know the complexity of Max Clique for, say, interval graphs. Since this is equivalent to Max Independent Set for the complement of interval graphs, you can look it up in ISGCI. Dec 12, 2010 at 20:23
• For some of the special case of Maximum Matching, you can again use ISGCI because Maximum Matching in G is equivalent to Maximum Independent Set in the line graph of G, and sometimes it is shown as linear-time computable (instead of polynomial-time computable) in ISGCI. But to use this method, you have to know the class of the line graphs of certain graphs. Dec 12, 2010 at 20:27