Paper by Erik D. Demaine

Reference:
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.

Abstract:
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.

Length:
The paper is 10 pages.

Availability:
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 September 21, 2014 by Erik Demaine.