The Ramsey numbers of squares of paths and cycles

Allen, Peter, Mergoni Cecchelli, Domenico, Skokan, Jozef and Roberts, Barnaby (2024) The Ramsey numbers of squares of paths and cycles. Electronic Journal of Combinatorics, 31 (2). ISSN 1077-8926

Text (Allen_ramsey-numbers-of-squares--published) - Published Version Available under License Creative Commons Attribution No Derivatives. Download (1MB)

• Author
• Author
• Scopus publication

Abstract

The square G 2 of a graph G is the graph on V (G) with a pair of vertices uv an edge whenever u and v have distance 1 or 2 in G. Given graphs G and H, the Ramsey number R(G, H) is the minimum N such that whenever the edges of the complete graph K N are coloured with red and blue, there exists either a red copy of G or a blue copy of H. We prove that for all sufficiently large n we have (Formula presented). We also show that for every γ > 0 and ∆ there exists β > 0 such that the following holds: If G can be coloured with three colours such that all colour classes have size at most n, the maximum degree of G is at most ∆, and G has bandwidth at most βn, then R(G, G) ≤ (3 + γ)n.

Item Type:	Article
Official URL:	https://www.combinatorics.org/ojs/index.php/eljc
Additional Information:	© 2024 The Author(s)
Divisions:	Mathematics
Subjects:	Q Science > QA Mathematics
Date Deposited:	26 Mar 2024 15:09
Last Modified:	26 Sep 2025 23:26
URI:	http://eprintstest.lse.ac.uk/id/eprint/122505

Actions (login required)

View Item