Multicoloured Erdős–Hajnal conjecture for graphs

About 1 year old · traced to

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 1≤s0≤s1\le s_0\le s and k≥1k\ge1, and every s0s_0-colouring c0c_0 of KkK_k, there exist δ,C>0\delta,C>0 such that, for all n∈Nn\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.

References

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.