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.

Published
2000-05-02
Article Number
N3