Generalised Ramsey Numbers with respect to Classes of Graphs

E.J. Cockayne1, O. Favaron2, P.J. P.Grobler3, C.M. Mynhardt3, J. Puech2
1Department of Mathematics, University of Victoria, Victoria, BC, Canada
2LRI, Université de Paris Sud, Orsay, France
3Department of Mathematics, University of South Africa, Pretoria, South Africa

Abstract

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