On a valence problem in extremal graph theory (Q2562797): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1175548 |
Set OpenAlex properties. |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Miklós Simmonovits / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56001754 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the connection between chromatic number, maximal clique and minimal degree of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5544083 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of linear graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Families of Non-disjoint subsets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5548826 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5781249 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(73)90126-x / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2121190404 / rank | |||
Normal rank |
Latest revision as of 09:49, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a valence problem in extremal graph theory |
scientific article |
Statements
On a valence problem in extremal graph theory (English)
0 references
1973
0 references
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\).
0 references
0 references