Multicoloured Erdős–Hajnal conjecture for graphs

Let KkK_k and KnK_n be complete graphs. An ss-colouring is an edge-colouring using colours in a set of at most ss colours; a colouring dd of KnK_n contains a colouring c0c_0 of KkK_k if there is an injection ψ:V(Kk)V(Kn)\psi:V(K_k)\to V(K_n) preserving all edge colours, and it is c0c_0-free otherwise.

Multicoloured Erdős–Hajnal conjecture. For all 1s0s1\le s_0\le s and k1k\ge1, and every s0s_0-colouring c0c_0 of KkK_k, there exist δ,C>0\delta,C>0 such that, for all nNn\in\mathbb N and every c0c_0-free ss-colouring cc of KnK_n, there are a colour i{1,,s}i\in\{1,\dotsc,s\} and a set XX of at least CnδCn^\delta vertices of KnK_n such that c(e)ic(e)\ne i for every edge ee with both ends in XX.

This is a multicoloured form of the induced Erdős–Hajnal problem. It is known for some particular forbidden colourings and infinite classes, but is wide open in general.

Sources & referencesView supporting material

Primary source

Carolyn Chun, James Dylan Douthitt, Wayne Ge, Tony Huynh, Matthew E. Kroeker and Peter Nelson, “Rainbow triangles and the Erdős-Hajnal problem in projective geometries”, arXiv:2505.13781 (2025).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.