Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 268.05121
Autor: Erdös, Paul; Simonovits, M.
Title: On a valence problem in extremal graph theory. (In English)
Source: Discrete Math. 5, 323-334 (1973).
Review: Vorliegende Arbeit bezieht sich auf nicht-orientierte, Schlingen und mehrfache Kanten nicht enhaltende Graphen. Bezeichne L einen solchen vom vollständigen p-Graphen Kp verschiedenen p-chromatischen Graphen, welcher eine Kante e so enthält, daß L-e ein (p-1)-chromatischer Graph ist. Als Hauptergebnis der vorliegenden Arbeit bewiesen die Verff., daß, wenn G solch ein n-punktiger Graph ist, der keinen L, jedoch Kp enhält, dann ist die minimale Gradzahl von G höchstens gleich n(1-1/(p-3/2))+o(1). Die Verff. bewiesen auch das Folgende: für einen n-punktigen, mindestens t-chromatischen, dreiecklosen Graphen ist die minimale Gradzahl \geq (1/3+o(1))n.
Reviewer: B.Andrásfai
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag