Generalised Ramsey Numbers with respect to Classes of Graphs

Abstract

Let ${\mathcal{H}}_1,\dots ,{\mathcal{H}}_t$ be classes of graphs. The class Ramsey number $R({\mathcal{H}}_1,\dots ,{\mathcal{H}}_t)$ is the smallest integer $n$ such that for each $t$-edge colouring $(G_1,\dots ,G_t)$ of $K_n$, there is at least one $i\in \{1,\dots ,t\}$ such that $G_i$ contains a subgraph $H_i\in {\mathcal{H}}_i$. We take $t=2$ and determine $R({\mathcal{G}}_l^1,{\mathcal{G}}_m^1)$ for all $2\le l\le m$ and $R({\mathcal{G}}_i^2,{\mathcal{G}}_m^2)$ for all $3\le l\le m$, where ${\mathcal{G}}_j^i$ consists of all edge-minimal graphs of order $j$ and minimum degree $i$.