Generalised Ramsey numbers for two sets of cycles

Abstract

We determine several generalised Ramsey numbers for two sets ${\Gamma }_1$ and ${\Gamma }_2$ of cycles, in particular, all generalised Ramsey numbers $R({\Gamma }_1,{\Gamma }_2)$ such that ${\Gamma }_1$ or ${\Gamma }_2$ contains a cycle of length at most $6$, or the shortest cycle in each set is even. This generalises previous results of Erdős, Faudree, Rosta, Rousseau, and Schelp from the 1970s. Notably, including both $C_3$ and $C_4$ in one of the sets, makes very little difference from including only $C_4$. Furthermore, we give a conjecture for the general case. We also describe many $({\Gamma }_1,{\Gamma }_2)$-avoiding graphs, including a complete characterisation of most $({\Gamma }_1,{\Gamma }_2)$-critical graphs, i.e., $({\Gamma }_1,{\Gamma }_2)$-avoiding graphs on $R({\Gamma }_1,{\Gamma }_2)-1$ vertices, such that ${\Gamma }_1$ or ${\Gamma }_2$ contains a cycle of length at most $5$. For length $4$, this is an easy extension of a recent result of Wu, Sun, and Radziszowski, in which $|{\Gamma }_1|=|{\Gamma }_2|=1$. For lengths $3$ and $5$, our results are new even in this special case. Keywords: generalised Ramsey number, critical graph, cycle, set of cycles

18 pages, 1 figure