The clique conjecture for unique-chromatic colourings
The clique conjecture for unique-chromatic colourings
Given an edge-colouring of , a copy of is unique-chromatic if some colour occupies exactly one edge of it. An edge-colouring is -unique if every copy of is unique-chromatic, and is the least number of colours in an -unique edge-colouring of .
Clique uniqueness conjecture. For every positive integer ,
The paper proves a polynomial lower bound for every non-complete graph without isolated vertices, so cliques are conjectured to be precisely the graphs admitting sub-polynomially many colours. The cases and are proved; the remaining clique cases are 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.