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

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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 arrows a small graph H, then every 'dense' subgraph of 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 where and G is an n-vertex graph with, then for every 2-edge-colouring of G, either there are cycles of every length of the same colour, or there are cycles of every even length 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-vertex graph G with minimum degree larger than arrows the path with 2n vertices. Moreover, it implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for where and every n-vertex graph G with, in each 2-edge-colouring of G there exists a monochromatic cycle of length at least 2t+r.

Original languageEnglish
Pages (from-to)109
Number of pages122
JournalCombinatorics Probability and Computing
Volume31
Issue number1
DOIs
Publication statusPublished - 2022
Externally publishedYes

Keywords

  • Ramsey number
  • Regularity Lemma
  • paths and cycles

Fingerprint

Dive into the research topics of 'Monochromatic paths and cycles in 2-edge-coloured graphs with large minimum degree'. Together they form a unique fingerprint.

Cite this