Attacking Hadwiger's conjecture via chordal partitions

Seminar/Forum

Room 107
Peter Hall

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, Monash University