Some remarks on the odd hadwiger’s conjecture
Some remarks on the odd hadwiger’s conjecture
复制标题
关于奇哈维格猜想的一些评论
DOI：
10.1007/s00493-007-2213-9
复制
发表时间：
2007
期刊：
影响因子：
1.1
通讯作者：
Zi
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi;Zi
如果H中有l个顶点不相交的树，使得每两个树都由一条边连接，并且树的所有顶点都是双色的，使得树内的边是双色的，但树之间的边是单色的，则我们说H有一个至少为l阶的奇完全子式。Gerards和Seymour猜想，如果一个图没有l阶的奇完全子式，则它是（l-1）-可着色的。这比哈德维格的著名猜想强得多。最近，Geelen等人证明了存在一个常数c使得任何不含奇Kk-子式的图都是ck-logk-可染的。然而，目前还不知道是否存在一个绝对常数c，使得任何不含奇Kk-子式的图都是ck-可染的.基于这些事实，本文首先证明，对任意k，存在一个常数f（k），使得每个至少f（k）个顶点的（496 k + 13）-连通图有一个大小至少为k的奇完全子图或一个阶至多为8 k的点集X使得G-X是二分的。由于任何二部图都不包含大小至少为3的奇数完全子式，因此第二个条件是必要的。这是Böhme等人的一个类似结果.我们还证明了每个n阶图G都有一个大小至少为n/2α（G）− 1的奇完全子图，其中α（G）表示G的独立数.这是Duchet和Meyniel的一个类似结果。对于α（G）= 3的情形，我们得到了一个较好的结果.
We say that H has an odd complete minor of order at least 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.Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l − 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd Kk-minor is ck√logk-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd Kk-minor is ck-colorable.Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G–X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al.We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) − 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3.