Hajos’ Conjecture is almost always true

Hajos’ Conjecture is almost always true

Tue, 03/05/2011
14:30 		Bruce Reed (McGill) Combinatorial Theory Seminar Add to calendar L3
Hajos’ Conjecture is almost always true
In 1961 Hajos conjectured that if a graph contains no subdivsion of a clique of order t then its chromatic number is less than t. In 1981, Erdos and Fajtlowicz showed that the conjecture is almost always false. We show it is almost always true. This is joint work with Keevash, Mohar, and McDiarmid.