scientific article; zbMATH DE number 19185

From MaRDI portal
Publication:3976614





[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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976614)