Date: Tuesday, 25 Iyar 5766 (May 23, '06)

Speaker: Maria Chudnovsky (Princeton/CMI)

Title: "Hadwiger's conjecture for quasi-line graphs"

Abstract:
---------
Hadwiger's conjecture states that every graph that cannot be colored with k
colors contains the complete graph on k+1 vertices as a minor. This
conjecture is known to be true for small values of k: k=2,3 are not
difficult, but the proof for k=4,5 uses the Four Color Theorem (Please note
that the case k=4 also implies the 4CT). Another known result on this
problem is the theorem of Bruce Reed and Paul Seymour, that says that all
line-graphs satisfy Hadwiger's conjecture.

A graph is a quasi-line graph if the neighbor set of every vertex is the
union of two cliques, and so every line graph is a quasi-line graph. In
joint work with Alexandra Ovetsky, we proved that every quasi-line graph
satisfies Hadwiger's conjecture, thus extending Reed and Seymour's result.
The proof uses a recent structure theorem for quasi-line graphs, obtained in
joint work with Paul Seymour.