Chromatic number, clique subdivisions and the conjectures of Hajós and Erdös-Fajtlowicz
Joint with Choongbum Lee and Benny Sudakow.
1. Hajós conjecture
Let be the chromatic number of a graph and the clique number.
Basic conjecture: .
Converse is false (see 5-cycle) but a variant may hold.
Hajós conjecture, 1961: If a graph contains no subdivision of , then it is -colorable.
It is a strengthening of Hadwiger’s conjecture an the 4-color theorem.
Disproved by Catlin in 1979 for . Erdös-Fajtlowicz realized that almost all graphs are strong counter-examples. Let maximum for which contains a subdivision of .
Theorem 1 (Erdös-Fajtlowicz 1981) The random graph almost surely satisfies
We wonder how bad the conjecture can fail.
Definition 2 maximum of over all -vertex graphs.
Erdös-Fajtlowicz showed that
and conjectured that this is the maximum possible. This is what we prove.
Theorem 3 (Fox-Lee-Sudakov)
1.1. Independence number and clique subdivision
The following are used in the proof.
Definition 4 minimum of over all -vertex graphs with independence number .
Theorem 5 (Fox-Lee-Sudakov)
This is tight for . Examples achieving
are due to Alon (pseudo-random triangle free graphs).
In the dense case, we rely on
Theorem 6 (Bollobás-Thomason, Komlós-Szemerédi) Let denote the number of edges in . Then
In the sparse case, in the complement of a maximum independant set, there is a large subset all of whose independent sets are pretty small.
For fixed , is it true that
We know it only for .
If , is it true that
It is a matter of gaining a log factor on Bollobás-Thomason, Komlós-Szemerédi.
1.4. Questions from the audience
Is there a simpler proof without the log factor ? Answer: yes, using Bollobás-Thomason, Komlós-Szemerédi.