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