The clique conjecture for unique-chromatic colourings

From papers

Given an edge-colouring of KnK_n, a copy of HH is unique-chromatic if some colour occupies exactly one edge of it. An edge-colouring is HH-unique if every copy of HH is unique-chromatic, and uH(n)u_H(n) is the least number of colours in an HH-unique edge-colouring of KnK_n.

Clique uniqueness conjecture. For every positive integer t2t\geq 2,

uKt(n)=no(1).u_{K_t}(n)=n^{o(1)}.

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 t=4t=4 and t=5t=5 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

No solutions have been posted yet.