Versteegen's even-decomposability conjecture
Versteegen's even-decomposability conjecture
Let be a graph with an even number of edges. It is even-decomposable if there is a sequence
with each induced graph having an even number of edges and an independent set in . Let denote the least number of colours in an edge-colouring of with no even-chromatic copy of .
Versteegen's conjecture. We have
if and only if is even-decomposable.
Versteegen proved the forward obstruction that even-decomposable graphs satisfy . Thus the conjecture asserts that this is the only obstruction to the sub-polynomial bound ; 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
Sign in to submit a solution.
No solutions have been posted yet.