Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 612.05046
Autor: Burr, Stefan A.; Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.; Gould, R.J.; Jacobson, M.S.
Title: Goodness of trees for generalized books. (In English)
Source: Graphs Comb. 3, 1-6 (1987).
Review: For any graph G, let p(G) denote the cardinality of the vertex set of G, let \chi(G) denote the vertex chromatic number of G and let s(G) denote the "chromatic surplus" of G, i.e. the smallest number of vertices in a color class under any \chi(G)-coloring of the vertices of G. For any pair of graphs F and G, r(F,G) is the least number N so that in every 2-coloring of the edges of KN either there is a copy of F with all of its edges in the first color class or a copy of G with all of its edges in the second color class.
It is easy to see that for connected graphs F and G with p(G) \geq s(F): r(F,G) \geq (\chi(F)-1)(p(g)-1)-s(F). We say that G is F-good if equality holds. The paper is devoted to a study of those graphs F for which all large trees are F-good. The results include: All sufficiently large trees are K(1,1,m1,...,M2)-good.
Reviewer: J.E.Graver
Classif.: * 05C55 Generalized Ramsey theory
Keywords: chromatic surplus; coloring; F-good
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag