Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  456.05047
Autor:  Burr, Stefan A.; Erdös, Paul
Title:  Generalized Ramsey numbers involving subdivision graphs, and related problems in graph theory. (In English)
Source:  Ann. Discrete Math. 9, 37-42 (1980).
Review:  If G and H are Graphs, r(G,H) denotes the smallest positive integer r so that if the edges of Kr, the complete graoh on r vertices, are colored with two colors, the there is either a copy of G with all of its edges colored with the forst color or a copy of H with all of its edges colored with the second color. V.Chvátal [J. Graph Theory 1, 93 (1977; Zbl 351.05120) proved that if T is any tree on n vertices, then r(T,K\ell) = (\ell-1)(n-1)+1. It is clear then that (\ell-1)(n-1)+1 is a lower bound for r(G,K\ell) where G is any connnected graph on n vertices. A connected graph G on n vertices for which r(G,K\ell) = (\ell-1)(n-1)+1 is said to be \ell-good. The subdivision graph of G, denoted by S(G), is formed by putting vertex on every edge of G. The authors prove that for n \geq 8, S(Kn) is 3-good. The actually show that, for n \geq 8, the graph consisting of the subdivision graph of Kn together with all of the edges of Kn is 3-good.
Reviewer:  J.E.Graver
Classif.:  * 05C55 Generalized Ramsey theory
Keywords:  generalized Ramsey numbers; subdivision graph
Citations:  Zbl.351.05120

© 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