Fox–Lee–Sudakov lower bound for topological cliques

At least 9 years old · documented by

Let GG be a graph, let χ(G)\chi(G) denote its chromatic number, and let σ(G)\sigma(G) be the largest integer tt such that GG contains a subdivision TKtTK_t.

Fox–Lee–Sudakov conjecture. There is a constant c>0c>0 such that every graph GG with χ(G)=k\chi(G)=k satisfies

σ(G)≥cklog⁡k.\sigma(G)\ge c\sqrt{k\log k}.

The conjecture gives a quantitative lower bound on the size of a topological clique in terms of chromatic number. The supplied source gives no evidence of resolution, so it remains open.

References

Primary source

Dawei He, Yan Wang and Xingxing Yu, “The Kelmans-Seymour conjecture IV: a proof”, arXiv:1612.07189 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.