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 ε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 Π2p-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 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 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 √log 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. 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.
展开▼
机译：众所周知（Feige和Kilian [24]，Hastad [39]），除非ε> 0，否则不能在多项式时间内对n 1-ε内的色数进行逼近。 coRP = NP。计算列表色数比确定色数困难得多。已知确定列表色数是否为k（其中k≥3）的问题是<< SUB> 2 p -完全[37]。在本文中，我们专注于图的次闭合和奇次闭合系列。这样做时，我们还可以分别考虑对于k的固定值不具有K k -minor的图和不具有奇数K k -minor的图。我们的主要结果是，对于不具有K k -minors的图的色数有一个多项式时间逼近算法，对于不具有奇数K的图的色数有一个多项式时间逼近算法。 k 个未成年人。它们的时间复杂度分别为O（n 3 ）和O（n 4 ）。该算法具有乘法误差O（√logk）和加法误差O（k），并且乘法误差仅发生在列表色数和色数分别为Θ（k）的图中。如果H中有l个顶点不相交的树，使得它们中的每两个顶点通过一条边连接在一起，并且树的所有顶点都采用两种颜色着色，使得树内的边是奇数的，则该奇次完全次次是双色的，但树之间的边缘是单色的。让我们观察到，对于k≤n / 2，完整的二部图K n / 2，n / 2 包含一个K k -minor，但另一方面，它对于任何k≥3，它不包含奇数K k -minor。奇数K 5 -minor-free图与离散优化的一个领域密切相关，后者正在寻找条件在这种情况下，给定的多面体具有整数顶点，因此整数优化问题可以作为线性程序来解决。参见[33，34，64]。另外，还考虑了著名的哈德维格猜想的奇数形式，请参见[28]。我们的主要思想涉及到预着色扩展。这个想法被用于许多结果。一个例子是托马森关于平面图上著名定理的证明[69]。对于第一个结果，以前最著名的近似是一个简单的O（k√logk）逼近算法，该算法保证了O（k√）的列表着色log k）K k 次要图的颜色。这是根据Kostochka [54，53]和Thomason [67，68]的结果得出的。第二个结果的最佳先前近似来自Geelen等人的最新结果。 [28]给出了O（k√logk）逼近算法。我们还将算法与著名的Hadwiger [38]猜想及其奇数版本相关。实际上，我们给出了O（n 3 ）算法来确定Hadwiger猜想的弱版本是否成立。在这里，通过Hadwiger猜想的弱版本，我们的意思是说任何27k色图都包含K k -minor的猜想。另外，我们将给出O（n 2500k ）算法来确定任何2500k色图是否包含奇数K k -minor。演示文稿包含两篇论文，这两篇论文合并到了这篇论文中。第一个由两位当前作者关于图的次闭合图类的结果组成，另一个由第一作者对图的奇次闭合图类的结果组成。
展开▼
