Home » Subject » Graph Theory » Extremal G.T.

Multicolour Erdős--Hajnal Conjecture

Importance: High ✭✭✭
Author(s): Erdos, Paul
Hajnal, Andras
Subject: Graph Theory
» Extremal Graph Theory
Keywords: ramsey theory
Recomm. for undergrads: no
Posted by: Jon Noel
on: October 10th, 2019
Conjecture   For every fixed $ k\geq2 $ and fixed colouring $ \chi $ of $ E(K_k) $ with $ m $ colours, there exists $ \varepsilon>0 $ such that every colouring of the edges of $ K_n $ contains either $ k $ vertices whose edges are coloured according to $ \chi $ or $ n^\varepsilon $ vertices whose edges are coloured with at most $ m-1 $ colours.

See [FGP].

Related problems

The Erdös-Hajnal Conjecture

Bibliography

[FGP] Jacob Fox, Andrey Grinshpun and János Pach: The Erdős–Hajnal conjecture for rainbow triangles, J. Combin. Theory, Series B. 111 (2016), 75--125.


* indicates original appearance(s) of problem.
add new comment