Note on Gy. Elekes's Conjectures Concerning Unavoidable Patterns in Proper Colorings

Vera Rosta


A counterexample is presented to Gy. Elekes's conjecture concerning the existence of long $2$-colored paths in properly colored graphs. A modified version of the conjecture is given and its connections to a problem of Erdős - Gyárfás and to Szemerédi's theorem are examined.

Full Text: PDF