欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Coloring Graphs with Forbidden Minors
时间  Datetime
2017-05-13 10:00 — 11:00 
地点  Venue
1106, Math Building
报告人  Speaker
ZI-Xia Song
单位  Affiliation
University of Central Florida
邀请人  Host
Zhang Xiaodong
报告摘要  Abstract

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.