Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  456.05046
Autor:  Burr, Stefan A.; Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.
Title:  Ramsey-minimal graphs for star-forests. (In English)
Source:  Discrete Math. 33, 227-237 (1981).
Review:  Let G and H denote two given graphs. A graph F is (G,H)-minimal of whenever each edge of F is coloured red or blue the red subgraph contains a copy of G or the blue subgraph contains a copy of B and, furthermore, no proper subgraph of F has this property. The pair (G,H) is Ramsey-finite or Ramsey-infinite according as there are a finite or infinite number of (G,H)-minimal graphs. The authors partially solve the problem of classifying the star-forests (i.e. forests of stars) G and H for which (G, H) is Ramsey-finite. They show, among other things, that if G and H are star-forests with no single-edge components, then (G,H) is Ramsey-finite if and only of both G and H are single stars with an odd number of edges.
Reviewer:  J.W.Moon
Classif.:  * 05C55 Generalized Ramsey theory
                   05C05 Trees
                   05C35 Extremal problems (graph theory)
Keywords:  edge colouring; generalized Ramsey number; Ramsey-minimal graphs; star- forests

© 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