No label defined (Q3976614)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 19185
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 19185 |
Statements
26 June 1992
0 references
Ramsey number
0 references
coloring
0 references
chromatic surplus
0 references
\(G\)-good graphs
0 references
0.86704016
0 references
0.86092573
0 references
0 references
[For the entire collection see Zbl 0734.00014.] Let \(\chi(G)\) denote the chromatic number of the graph \(G\). Then \(s(G)\), the chromatic surplus, is defined to be the largest number \(s\) so that, in each \(\chi(G)\)-coloring of \(G\), every color class contains at least \(s\) vertices. The Ramsey number \(r(G,H)\) is defined to be the smallest positive integer \(r\) so that every two coloring of the edges of the complete graph \(K_ t\) has either a copy \(G\) with all of its edges colored with the first color or a copy of \(H\) with all of its edges colored with the second color. If \(r(G,H)=(\chi(G)-1)(| V(H)|- 1)+s(G)\) for a connected graph \(H\), then \(H\) is said to be \(G\)-good. This paper contains a survey of known results about the chromatic surplus and \(G\)-good graphs. It ends with a listing of several interesting open questions about those concepts.
0 references