TY - JOUR

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

AU - Balog, Jozsef

AU - Kostochka, Alexandr

AU - Lavrov, Mikhail

AU - Liu, Xujun

N1 - Publisher Copyright:
© The Author(s), 2021. Published by Cambridge University Press.

PY - 2021

Y1 - 2021

N2 - A graph G arrows a graph H if in every 2-edge-colouring of G there exists a monochromatic copy of H. Schelp had the idea that if the complete graph Kn arrows a small graph H, then every 'dense' subgraph of Kn 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 = 3t+r where r ∈ {0,1,2} and G is an n-vertex graph with δ(G) ≥ (3n-1)/4, then for every 2-edge-colouring of G, either there are cycles of every length {3, 4, 5, ⋯, 2t+r} of the same colour, or there are cycles of every even length {4, 6, 8, ⋯, 2t+2} of the samecolour. Our result is tight in the sense that no longer cycles (of length >2t+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 (3t-1)-vertex graph G with minimum degree larger than 3|V(G)|/4 arrows the path P2n with 2n vertices. Moreover, it implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for n = 3t + r where r ∈ {0,1,2} and every n-vertex graph G with δ(G) ≥ 3n/4, in each 2-edge-colouring of G there exists a monochromatic cycle of length at least 2t + r.

AB - A graph G arrows a graph H if in every 2-edge-colouring of G there exists a monochromatic copy of H. Schelp had the idea that if the complete graph Kn arrows a small graph H, then every 'dense' subgraph of Kn 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 = 3t+r where r ∈ {0,1,2} and G is an n-vertex graph with δ(G) ≥ (3n-1)/4, then for every 2-edge-colouring of G, either there are cycles of every length {3, 4, 5, ⋯, 2t+r} of the same colour, or there are cycles of every even length {4, 6, 8, ⋯, 2t+2} of the samecolour. Our result is tight in the sense that no longer cycles (of length >2t+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 (3t-1)-vertex graph G with minimum degree larger than 3|V(G)|/4 arrows the path P2n with 2n vertices. Moreover, it implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for n = 3t + r where r ∈ {0,1,2} and every n-vertex graph G with δ(G) ≥ 3n/4, in each 2-edge-colouring of G there exists a monochromatic cycle of length at least 2t + r.

KW - paths and cycles

KW - Ramsey number

KW - Regularity Lemma

UR - http://www.scopus.com/inward/record.url?scp=85108059795&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108059795&partnerID=8YFLogxK

U2 - 10.1017/S0963548321000201

DO - 10.1017/S0963548321000201

M3 - Article

AN - SCOPUS:85108059795

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

ER -