期刊
JOURNAL OF COMBINATORIAL THEORY SERIES B
卷 127, 期 -, 页码 14-31出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2017.05.001
关键词
Hadwiger's conjecture; Graph minor; Contraction-critical graph
类别
Hadwiger's conjecture from 1943 states that for every integer t >= 1, every graph either can be t-colored or has a subgraph that can be contracted to the complete graph on t+1 vertices. As pointed out by Paul Seymour in his recent survey on Hadwiger's conjecture, proving that graphs with no K-7 minor are 6-colorable is the first case of Hadwiger's conjecture that is still open. It is not known yet whether graphs with no K-7 minor are 7-colorable. Using a Kempe-chain argument along with the fact that an induced path on three vertices is dominating in a graph with independence number two, we first give a very short and computer-free proof of a recent result of Albar and Gongalves and generalize it to the next step by showing that every graph with no K-t minor is (2t - 6)-colorable, where t is an element of {7, 8, 9}. We then prove that graphs with K-8(-) minor are 9-colorable, and graphs with no K-8(=) minor are 8-colorable. Finally we prove that if Mader's bound for the extremal function for K-t minors is true, then every graph with no K-t minor is (2t - 6)-colorable for all t >= 6. This implies our first result. We believe that the Kempe-chain method we have developed in this paper is of independent interest. (C) 2017 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据