Versteegen's even-decomposability conjecture

From papers

Let HH be a graph with an even number of edges. It is even-decomposable if there is a sequence

V(H)=V0\V1\\Vk=V(H)=V_0\backslash V_1\backslash\cdots\backslash V_k=\emptyset

with each induced graph H[Vi]H[V_i] having an even number of edges and Vi\Vi+1V_i\backslash V_{i+1} an independent set in HH. Let rH(n)r_H(n) denote the least number of colours in an edge-colouring of KnK_n with no even-chromatic copy of HH.

Versteegen's conjecture. We have

rH(n)=nΩ(1)r_H(n)=n^{\Omega(1)}

if and only if HH is even-decomposable.

Versteegen proved the forward obstruction that even-decomposable graphs satisfy rH(n)=nΩ(1)r_H(n)=n^{\Omega(1)}. Thus the conjecture asserts that this is the only obstruction to the sub-polynomial bound rH(n)=no(1)r_H(n)=n^{o(1)}; it remains open.

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

Fredy Yip, “A variant of the Erdős-Gyárfás problem for K_8”, arXiv:2409.16778 (2025).

Solutions 0

No solutions have been posted yet.