Fox–Lee–Sudakov lower bound for topological cliques

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)cklogk.\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.

Sources & referencesView supporting material

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.