**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 Π_{2}^{p}-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

*K*_{k}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.

Last updated July 23, 2024 by Erik Demaine.