Ramsey goodness and generalized stars (Q976142)

Given a graph \(G\) with chromatic number \(\chi(G)\) and chromatic surplus \(s = s(G)\), a graph \(H\) is said to be \(G\)-good if the Ramsey number \(r(G,H)\) satisfies \[ r(G, H) = (\chi(G) - 1)(|H| - 1) + s. \] For arbitrary graphs \(G\) and \(H\), the related graphs \(K_1 + G\) and \(K_1 + nH\) are considered with \(s = s(G)\) and \(h = |H|\), and the following is proved: \[ r(K_1 + G, K_1 = nH) \leq \chi(G)(hn + s - 1) + 1, \] for large \(n\). In particular, \[ r(K_1 + K_k(s), K_1 + nH) = \chi(G)(hn + s - 1) + 1, \] if \(hn\) is odd, and \(K_k(s)\) is the complete \(k\)-partite graph with \(s\) vertices in each part. This implies, in particular, that \(K_{1,n}\) is not \(K_1 + K_k(s)\)-good or \(K_k(s)\)-good for \(n\) odd and \(s \geq 2\). Ramsey numbers for specific families of graphs, such as fans and wheels are corollaries of this result.