BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Coloring graphs with forbidden minors Song, Zixia


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International