SEMINARS
Coloring Graphs with Forbidden Minors

2017-05-13　10:00 — 11:00

1106, Math Building

ZI-Xia Song

University of Central Florida

Zhang Xiaodong

Hadwiger's conjecture from 1943 states that for every integer $t\ge1$,  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 Gon\c calves 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. We believe that the Kempe-chain method we have developed in proving these results is of independent interest. \\

This is joint work with Martin Rolek.