##
**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 K_{r}, 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(K_{n}) is 3-good. The actually show that, for n \geq 8, the graph consisting of the subdivision graph of K_{n} together with all of the edges of K_{n} 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