Ramsey numbers for a disjoint union of good graphs (Q968423): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: The Ramsey numbers for disjoint unions of trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ramsey numbers for a disjoint union of some graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4120601 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: All Ramsey numbers for cycles in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Ramsey Number <i>r</i>(<i>F</i>, <i>K</i><sub>m</sub>) Where <i>F</i> is a Forest / rank | |||
Normal rank |
Latest revision as of 19:48, 2 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ramsey numbers for a disjoint union of good graphs |
scientific article |
Statements
Ramsey numbers for a disjoint union of good graphs (English)
0 references
5 May 2010
0 references
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\).
0 references
tree
0 references
complete graph
0 references
forest
0 references
\(g\)-good graph
0 references
Ramsey number
0 references