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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page