Monochromatic paths and cycles in 2-edge-colored graphs with large minimum degree

Abstract: A graph

G

arrows a graph

H

if in every

2

-edge-coloring of

G

there exists a monochromatic copy of

H

. Schelp had the idea that if the complete graph

K_{n}

arrows a small graph

H

, then every "dense" subgraph of

K_{n}

also arrows

H

, and he outlined some problems in this direction. Our main result is in this spirit. We prove that for every sufficiently large

n

, if

n = 3 t + r

where

r i n 0, 1, 2

and

G

is an

n

-vertex graph with

d e l t a (G) g e (3 n - 1) / 4

, then for every

2

-edge-coloring of

G

, either there are cycles of every length

3, 4, 5, d o t s, 2 t + r

of the same color, or there are cycles of every even length

4, 6, 8, d o t s, 2 t + 2

of the same color. Our result is tight in the sense that no longer cycles (of length

> 2 t + r

) can be guaranteed and the minimum degree condition cannot be reduced. It also implies the conjecture of Schelp that for every sufficiently large

n

, every

(3 t - 1)

-vertex graph

G

with minimum degree larger than

3 | V (G) | / 4

arrows the path

P_{2 n}

with

2 n

vertices. Moreover, it implies for sufficiently large

n

the conjecture by Benevides, {L}uczak, Scott, Skokan and White that for

n = 3 t + r

where

r i n 0, 1, 2

and every

n

-vertex graph

G

with

d e l t a (G) g e 3 n / 4

, in each

2

-edge-coloring of

G

there exists a monochromatic cycle of length at least

2 t + r

.

This page was built for publication: Monochromatic paths and cycles in $2$-edge-colored graphs with large minimum degree