** 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).

** 1.2. Tools **

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.

** 1.3. Conjectures **

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.

### Like this:

Like Loading...

*Related*

## About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri PoincarĂ©, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
http://www.math.ens.fr/metric2011/