Treffer: Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs

It is well-known (Feige and Kilian [24], Hastad [39]) that approximating the chromatic number within a factor of n1-ε cannot be done in polynomial time for e > 0, unless coRP = NP. Computing the list-chromatic number is much harder than determining the chromatic number. It is known that the problem of deciding if the list-chromatic number is k, where k > 3, is Πp2-complete [37]. In this paper, we focus on minor-closed and odd-minor-closed families of graphs. In doing that, we may as well consider only graphs without Kk-minors and graphs without odd Kk-minors for a fixed value of k, respectively. Our main results are that there is a polynomial time approximation algorithm for the list-chromatic number of graphs without Kk-minors and there is a polynomial time approximation algorithm for the chromatic number of graphs without odd-Kk-minors. Their time complexity is O(n3) and O(n4), respectively. The algorithms have multiplicative error O(√log k) and additive error O(k), and the multiplicative error occurs only for graphs whose list-chromatic number and chromatic number are Θ(k), respectively. Let us recall that H has an odd complete minor of order l if there are I vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Let us observe that the complete bipartite graph Kn/2,n/2 contains a Kk-minor for k < n/2, but on the other hand, it does not contain an odd Kk-minor for any k > 3. Odd K5-minor-free graphs are closely related to one field of discrete optimization which is finding conditions under which a given polyhedron has integer vertices, so that integer optimization problems can be solved as linear programs. See [33, 34, 64]. Also, the odd version of the well-known Hadwiger's conjecture has been considered, see [28]. Our main idea involves precoloring extension. This idea is used in many results; one example is Thomassen's proof on his celebrated theorem on planar graphs [69]. The best previously known approximation for the first result is a simple O(k√log k)-approximation following algorithm that guarantees a list-coloring with O(k√log k) colors for Kk-minor-free graphs. This follows from results of Kostochka [54, 53] and Thomason [67, 68]. The best previous approximation for the second result comes from the recent result of Geelen et al. [28] who gave an O(k√og k)-approximation algorithm. We also relate our algorithm to the well-known conjecture of Hadwiger [38] and its odd version. In fact, we give an O(n3) algorithm to decide whether or not a weaker version of Hadwiger's conjecture is true. Here, by a weaker version of Hadwiger's conjecture, we mean a conjecture which says that any 27k-chromatic graph contains a Kk-minor. Also, we shall give an O(n2500k) algorithm for deciding whether or not any 2500k-chromatic graph contains an odd-Kk-minor. Let us mention that this presentation consists of two papers which are merged into this one.