Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 231.05110
Autor: Erdös, Pál
Title: On the graph-theorem of Pál Turán. (In Hungarian)
Source: Mat. Lapok 21 (1970), 249-251 (1971).
Review: Let Gn be a graph of n vertices, x1, ... ,xn. Assume v(x1) \geq v(x2) \geq ... \geq v(xn) where v(x) is the valency of the vertex x. Assume that Gn does not contain a complete subgraph of r vertices. The author proves that there is a graph G'n having chromatic number r-1 for which v(yi) \geq v(xi), i = 1, ... ,n (y1, ... ,yn are the vertices of Gn). The method is essentially identical with that of B. Andrásfai [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 193-196 (1962; Zbl 114.40001)].
Classif.: * 05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag