Multicoloured Erdős–Hajnal conjecture for graphs
Let and be complete graphs. An -colouring is an edge-colouring using colours in a set of at most colours; a colouring of contains a colouring of if there is an injection preserving all edge colours, and it is -free otherwise.
Multicoloured Erdős–Hajnal conjecture. For all and , and every -colouring of , there exist such that, for all and every -free -colouring of , there are a colour and a set of at least vertices of such that for every edge with both ends in .
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
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.