Multicoloured Erdős–Hajnal conjecture for graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.