On a valence problem in extremal graph theory (Q2562797)

Vorliegende Arbeit bezieht sich auf nicht-orientierte, Schlingen und mehrfache Kanten nicht enhaltende Graphen. Bezeichne \(L\) einen solchen vom vollständigen \(p\)-Graphen \(K_p\) 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 \(K_p\) enhält, dann ist die minimale Gradzahl von \(G\) höchstens gleich \(n(1-1/(p-3/2))+{\mathfrak 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+{\mathfrak o}(1))n\).