Paper by Erik D. Demaine

Ken-ichi Kawarabayashi, Erik D. Demaine, and MohammadTaghi Hajiaghayi, “Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs”, in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, New York, January 4–6, 2009, pages 1166–1175.

It is known that computing the list chromatic number is harder than computing the chromatic number (assuming NP ≠ coNP). In fact, the problem of deciding whether a given graph is f-list-colorable for a function f : V → {c − 1, c} for c ≥ 3 is Π2p-complete. In general, it is believed that approximating list coloring is hard for dense graphs.

In this paper, we are interested in sparse graphs. More specifically, we deal with nontrivial minor-closed classes of graphs, i.e., graphs excluding some Kk minor. We refine the seminal structure theorem of Robertson and Seymour, and then give an additive approximation for list-coloring within k − 2 of the list chromatic number. This improves the previous multiplicative O(k)-approximation algorithm [20]. Clearly our result also yields an additive approximation algorithm for graph coloring in a minor-closed graph class. This result may give better graph colorings than the previous multiplicative 2-approximation algorithm for graph coloring in a minor-closed graph class [6].

Our structure theorem is of independent interest in the sense that it gives rise to a new insight on well-connected H-minor-free graphs. In particular, this class of graphs can be easily decomposed into two parts so that one part has bounded treewidth and the other part is a disjoint union of bounded-genus graphs. Moreover, we can control the number of edges between the two parts. The proof method itself tells us how knowledge of a local structure can be used to gain a global structure, which gives new insight on how to decompose a graph with the help of local-structure information.

The paper is 10 pages.

The paper is available in PostScript (276k), gzipped PostScript (114k), and PDF (206k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated April 8, 2014 by Erik Demaine.