The chromatic-number conjecture for clique immersions

From papers

Let GG be a graph, let χ(G)\chi(G) be its chromatic number, and let KkK_k denote the complete graph on kk vertices. Clique-immersion conjecture. If

χ(G)k,\chi(G)\geq k,

then GG contains a KkK_k-immersion. This would identify the chromatic number as sufficient for a complete-graph immersion; the source presents it as open and notes that the answer to the relevant average-degree question might be kk.

Progress summary

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

Sources & referencesView supporting material

Primary source

Shoham Letzter, “Sublinear expanders and their applications”, arXiv:2401.10865 (2024).

Solutions 0

No solutions have been posted yet.