A natural generalisation in graph Ramsey theory

Alexander Haupt; Damian Reding

paper

A natural generalisation in graph Ramsey theory

arXiv:1708.07060

Abstract

In this note we study graphs $G_{r}$ with the property that every colouring of $E (G_{r})$ with $r + 1$ colours admits a copy of some graph $H$ using at most $r$ colours. For $1 \leq r \leq e (H)$ such graphs occur naturally at intermediate steps in the synthesis of a $2$ -colour Ramsey graph $G_{1} ⟶ H$ . (The corresponding notion of Ramsey-type numbers was introduced by Erdös, Hajnal and Rado in 1965 and subsequently studied by Erdös and Szemerédi in 1972). For $H = K_{n}$ we prove a result on building a $G_{r}$ from a $G_{r + 1}$ and establish Ramsey-infiniteness. From the structural point of view, we characterise the class of the minimal $G_{r}$ in the case when $H$ is relaxed to be the graph property of containing a cycle; we then use it to progress towards a constructive description of that class by proving both a reduction and an extension theorem.

8 pages