Publications of Paul Erdos

Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No: 161.43305
Autor: Erdös, Pál; Gallai, Tibor
Title: Solution of a problem of Dirac (In English)
Source: Theory Graphs Appl., Proc. Symp. Smolenice 1963, 167-168 (1964).
Review: We quote the authors. "In a graph-theoretic colloquium at Smolenice, G.A.Dirac conjectured (see ibid. p. 167 problem 5) that the chromatic number of a proper regular subgraph of a complete n-gon is \leq 3n/5. We shall prove this conjecture. In fact we shall prove the following theorem (G⁽ⁿ⁾ always denotes a graph with n vertices). Theorem. Let G⁽ⁿ⁾ be a regular graph of valence r < n-1 and chromatic number k. Then k \leq 3n/5, with equality if and only if the components of the complementary graph \overline{G⁽ⁿ⁾} of G⁽ⁿ⁾ are pentagons."
Reviewer: R.L.Hemminger
Index Words: topology

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.

Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry

Probabability Personalia About Paul Erdös Publication Year Home Page

Books	Problems	Set Theory	Combinatorics	Extremal Probl/Ramsey Th.
Graph Theory	Add.Number Theory	Mult.Number Theory	Analysis	Geometry
Probabability	Personalia	About Paul Erdös	Publication Year	Home Page