Attacking Hadwiger's conjecture via chordal partitions

Seminar/Forum

Attacking Hadwiger's conjecture via chordal partitions

Room 107
Peter Hall
Monash Road

Map

More information

sanming@unimelb.edu.au

Hadwiger's Conjecture asserts that every graph with no \(Kt\)-minor is \((t-1)\)-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}{2t-1}\) [Duchet and Meyniel],

-- are fractionally \((2t-1)\)-colourable [Reed and Seymour], and

-- are \((t-1)\)-colouable with bounded defect, and \((2t-2)\)-colourable with bounded clustering [Van den Heuvel and Wood].

The unifying theme of these proofs is the use of chordal partitions. The take-home message is that chordal partitions provide an approach for studying \(K_t\)-minor-free 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
    Professor David Wood, Monash University