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.