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