Ramsey numbers for a disjoint union of good graphs (Q968423): Difference between revisions

A graph \(H\) is \(G\)-good if the Ramsey number \(R(H, G) = (\chi(G) - 1)(|V(H)| - 1) + s(G)\), where \(s(G)\) is the chromatic surplus of \(G\). The Ramsey number \( R(F, G)\) is considered where \(F\) is a graph in which each component is a \(G\)-good graph. Let \(c(F)\) denote the largest component of \(F\) and \(k_i\) the number of components of \(F\) of order \(i\). It is shown that \[ R(F, G) = \max_{1 \leq j \leq c(F)} \left\{(j - 1)(\chi(G) - 2) + \sum_{i=j}^{c(F)} ik_i(F)\right\} + s(G) - 1. \] More specifically, for connected \(G\)-good graphs it is shown that \(R(C_{5, t}, C_5) = 2t + 9\) for \(t \geq 0\), and \(R(C_{5, t}, 2C_5) = 2t + 10\) for \(t \geq 2\), where \(C(5, t)\) is the graph obtained from \(C_5 \cup \overline{K}_t\) by adding all edges from one vertex of \(C_5\) to the vertices of \(\overline{K}_t\).