Akademska digitalna zbirka SLovenije - logo
(UL)
  • Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
    Kawarabayashi, Ken-ichi ; Mohar, Bojan, 1956-
    It is well-known (Feige and Kilian, H\aa stad) that approximating the chromatic number within a factor of ▫$n^{1-\varepsilon}$▫ cannot be done in polynomial time for ▫$\varepsilon > 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 \geq 3$▫, is ▫$\Pi_2^p$▫-complete. 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 ▫$K_k$▫-minors and graphs without odd ▫$K_k$▫-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 ▫$K_k$▫-minors and there is a polynomial time approximation algorithm for the chromatic number of graphs without odd-▫$K_k$▫-minors. Their time complexity is ▫$O(n^3)$▫ and ▫$O(n^4)$▫, respectively. The algorithms have multiplicative error ▫$O(\sqrt{\log k})$▫ and additive error ▫$O(k)$▫, and the multiplicative error occurs only for graphs whose list-chromatic number and chromatic number are ▫$\Theta(k)$▫, respectively. Let us recall that ▫$H$▫ has an odd complete minor of order ▫$l$▫ if there are ▫$l$▫ 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 ▫$K_{n/2,n/2}$▫ contains a ▫$K_k$▫-minor for ▫$k \leq n/2$▫, but on the other hand, it does not contain an odd ▫$K_k$▫-minor for any ▫$k \geq 3$▫. Odd ▫$K_5$▫-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. Also, the odd version of the well-known Hadwiger's conjecturehas been considered. The best previously known approximation for the first result is a simple ▫$O(k \sqrt{\log k})$▫-approximation following algorithm that guarantees a list-coloring with ▫$O(k \sqrt{\log k})$▫ colors for ▫$K_k$▫-minor-free graphs. This follows from results of Kostochka and Thomason. The best previous approximation for the second result comes from the recent result of Geelen et al. who gave an ▫$O(k \sqrt{\log k})$▫-approximation algorithm. We also relate our algorithm to the well-known conjecture of Hadwiger and its odd version. In fact, we give an ▫$O(n^3)$▫ 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 ▫$K_k$▫-minor. Also, we shall give an ▫$O(n^{2500k})$▫ algorithm for deciding whether or not any ▫$2500k$▫-chromatic graph contains an odd-▫$K_k$▫-minor. Let us mention that this presentation consists of two papers which are merged into this one. The first one consists of results concerning minor-closed classes of graphs by two current authors, and the other consists of results concerning odd-minor-closed classes of graphs by the first author.
    Vir: STOC'06 : proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, Washington, USA, May 21-23, 2006 (Str. 401-416)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2006
    Jezik - angleški
    COBISS.SI-ID - 14128473

    Povezava(-e):

    http://doi.acm.org/10.1145/1132516.1132576

Vnos na polico