Any 7-Chromatic Graphs Has K7 Or K4,4 As A Minor
Any 7-Chromatic Graphs Has K7 Or K4,4 As A Minor
复制标题
任何 7 色图都有 K7 或 K4,4 作为小调
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
B. Toft
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi;B. Toft
1943年，哈德维格提出了每一个k色图都有一个kk小调的猜想。这个猜想也许是所有图论中最有趣的猜想。众所周知，k=5的情况等价于Wagner[39]在1937年证明的四色定理。大约60年后，Robertson、Seymour和Thomas b[29]证明了k=6的情形也等价于四色定理。到目前为止，k≥7的病例仍然是开放的，即使是k=7的病例，到目前为止，我们也几乎没有希望验证。事实上，关于七色图的定理只有几个，例如[17]。在本文中，我们不使用四色定理[1,2,28]，证明了标题中所述的深层结果。这一结果验证了(m,1)-Minor猜想的第一个未解决的情况m=6，该猜想是Hadwiger猜想的一种弱形式，也是Chartrand et al.[8]（1971）和Woodall[42]（1990）的更一般猜想的一种特例。这个证明有点长，并且使用了Jørgensen[20]、Mader[23]和Robertson、Seymour和Thomas[29]的较早的深入结果和方法。
In 1943, Hadwiger made the conjecture that every k-chromatic graph has a Kk-minor. This conjecture is, perhaps, the most interesting conjecture of all graph theory. It is well known that the case k=5 is equivalent to the Four Colour Theorem, as proved by Wagner [39] in 1937. About 60 years later, Robertson, Seymour and Thomas [29] proved that the case k=6 is also equivalent to the Four Colour Theorem. So far, the cases k≥7 are still open and we have little hope to verify even the case k=7 up to now. In fact, there are only a few theorems concerning 7-chromatic graphs, e. g. [17].In this paper, we prove the deep result stated in the title, without using the Four Colour Theorem [1,2,28]. This result verifies the first unsettled case m=6 of the (m,1)-Minor Conjecture which is a weaker form of Hadwiger’s Conjecture and a special case of a more general conjecture of Chartrand et al. [8] in 1971 and Woodall [42] in 1990.The proof is somewhat long and uses earlier deep results and methods of Jørgensen [20], Mader [23], and Robertson, Seymour and Thomas [29].