Premium
Ramsey numbers of trails and circuits
Author(s) -
Conlon David,
Tyomkyn Mykhaylo
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22865
Subject(s) - monochromatic color , mathematics , combinatorics , graph , electronic circuit , ramsey's theorem , discrete mathematics , complete graph , physics , quantum mechanics , optics
Abstract We show that every two‐colouring of the edges of the complete graphK n${K}_{n}$ contains a monochromatic trail or circuit of length at least2 n 2 ∕ 9 + o ( n 2 )$2{n}^{2}\unicode{x02215}9+o({n}^{2})$ , which is asymptotically best possible.