Ramsey numbers for a disjoint union of good graphs
type: Item
instance of: scholarly article
title: Ramsey numbers for a disjoint union of good graphs
zbMATH Open document ID: 1215.05110
author: Halina Bielak
published in: Discrete Mathematics
publication date: 2010-05-05T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 5703950
zbMATH Keywords: tree
zbMATH Keywords: complete graph
zbMATH Keywords: forest
zbMATH Keywords: \(g\)-good graph
zbMATH Keywords: Ramsey number
reviewed by: Ralph Faudree
MaRDI profile type: Publication
full work available at URL: j.disc.2009.12.001
OpenAlex ID: W2083888362
cites work: The Ramsey numbers for disjoint unions of trees
cites work: Ramsey numbers for a disjoint union of some graphs
cites work: Q4120601
cites work: All Ramsey numbers for cycles in graphs
cites work: On the Ramsey Number r(F, Km) Where F is a Forest
DOI: 10.1016/J.DISC.2009.12.001
description: scientific article; zbMATH DE number 5703950