Open Collections

Coloring graphs with forbidden minors

Banff International Research Station for Mathematical Innovation and Discovery

As pointed out by 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 Goncalves, and generalize it to the next step by showing that every graph with no \(K_t\) minor is \((2t-6)\)-colorable, where \(t\in\{7,8,9\}\). We then prove that graphs with no \(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\ge6\). This implies our first result. This is joint work with Martin Rolek.

Mathematics; Combinatorics; Computer science; Discrete mathematics

video/mp4

Author affiliation: University of Central Florida

2018-04-09

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65183

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/