Long monochromatic paths and cycles in $2$-edge-colored graphs with large minimum degree

József Balogh, Alexandr Kostochka, Mikhail Lavrov, Xujun Liu

Published 2019-06-07Version 1

Our main result is a proof for sufficiently large $n$ of the conjecture by Benevides, \L uczak, Scott, Skokan and White that for every positive integer $n$ of the form $n=3t+r$ where $r \in \{0,1,2\}$ and every $n$-vertex graph $G$ with $\delta(G) \ge 3n/4$, in each $2$-edge-coloring of $G$ there exists a monochromatic cycle of length at least $2t+r$. Our result implies the conjecture of Schelp that for every sufficiently large $n$, every $(3n-1)$-vertex graph $G$ with minimum degree larger than $3|V(G)|/4$, in every $2$-edge-coloring of $G$, there is a monochromatic path with $2n$ vertices.