On Ramsey-type problems for paths and cycles with few colour changes

Abstract

In 1967, Gerencser and Gyárfás determined the exact values of the two-colour Ramsey numbers of paths. In a footnote, they made the following observation: Every $2$-edge-coloured complete graph contains a Hamilton path with at most one colour change. Later, this led to a challenging and still wide open conjecture about covering edge-coloured complete graphs with monochromatic paths. Inspired by the original statement, we study paths and cycles with few colour changes in $3$-edge-coloured complete graphs. For this, we introduce a new Ramsey-type parameter: For $q,k\in \mathbb{N}$ and a graph $G$, let $R_q^k(G)$ denote the smallest $N\in \mathbb{N}$ such that every $q$-edge-coloured complete graph on $N$ vertices contains a copy of $G$ with at most $k$ vertices that are incident to edges in $G$ of different colours. For paths, we show that $R_3^1(P_n)=\frac{3n}{2}+O(1)$, and for even cycles, we show that $R_3^2(C_n)=\frac{3n}{2}+o(n)$.

20 pages, 1 figure