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

Vera Rosta

Abstract


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