most recent 30 from http://mathoverflow.net 2013-05-20T08:15:43Z http://mathoverflow.net/feeds/user/23539 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10468/algorithms-on-graphs-of-bounded-degeneracy-arboricity/96327#96327 Martin Vatshelle 2012-05-08T11:24:49Z 2012-05-08T11:24:49Z

<p>There is one more approach to solve problems like Max Clique on graphs of bounded degeneracy. You can look at the complement graph of a graph $G$ (i.e. every edge is a non-edge and every non-edge is an edge). Solving Max Clique on $G$ is the same as solving Max Independent set on the complement.</p> <p>For the complement of bounded degeneracy graphs algorithms for many problems are known. E.g. Maximum Independent Set, Minimum Dominating Set, Perfect Code, k-Coloring, H- Cover, H-Homomorphism and H-Role Assignment are FPT parameterized by the degeneracy of the complement. See <a href="http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf" rel="nofollow">http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf</a> (submitted to journal)</p> <p>Some of these problems make sense to translate to the complement graph, such as:</p> <p>Can G be colored with $k$ colors -> can the complement be covered by $k$ cliques? (fixed $k$)</p> <p>Is there an $3$-regular induced subgraph of $G$ -> is there an induced $k$ regular subgraph of the complement on $k+4$ vertices?</p>