Attacking Hadwiger's conjecture via chordal partitions
Seminar/Forum
Hadwiger's Conjecture asserts that every graph with no \(Kt\)minor is \((t1)\)colourable. This is widely considered to be one of the most important conjectures in graph theory. It is even open whether every graph with no \(Kt\)minor is \(O(t)\)colourable. This talk will describe four results, each of which can be considered as a step in the direction of Hadwiger's conjecture. These results state that graphs with no \(K_t\)minor:
 have stable sets of size at least \(\frac{n}{2t1}\) [Duchet and Meyniel],
 are fractionally \((2t1)\)colourable [Reed and Seymour], and
 are \((t1)\)colouable with bounded defect, and \((2t2)\)colourable with bounded clustering [Van den Heuvel and Wood].
The unifying theme of these proofs is the use of chordal partitions. The takehome message is that chordal partitions provide an approach for studying \(K_t\)minorfree graphs that is much simpler than the graph minor structure theorem.
Other information: This talk will be broadcast online using Zoom conferencing system. Join from PC, Mac, iOS or Android: https://unimelb.zoom.us/j/988903148
Presenter

Professor David Wood, Monash University