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.

BibTeX

@InProceedings{ListColoring_SODA2009,
  AUTHOR        = {Ken-ichi Kawarabayashi and Erik D. Demaine and
                   MohammadTaghi Hajiaghayi},
  TITLE         = {Additive Approximation Algorithms for
                   List-Coloring Minor-Closed Class of Graphs},
  BOOKTITLE     = {Proceedings of the 20th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2009)},
  bookurl       = {http://www.siam.org/meetings/da09/},
  ADDRESS       = {New York, New York},
  MONTH         = {January 4--6},
  YEAR          = 2009,
  PAGES         = {1166--1175},

  length        = {10 pages},
  dblp          = {https://dblp.org/rec/conf/soda/KawarabayashiDH09},
  doi           = {https://dx.doi.org/10.1137/1.9781611973068.126},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1137/1.9781611973068.126">SIAM</A>.},
}

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 Π₂^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.

Comments:

This paper is also available from SIAM.

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]