Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  378.05032
Autor:  Erdös, Paul; Wilson, Robin J.
Title:  On the chromatic index of almost all graphs. (In English)
Source:  J. Comb. Theory, Ser. B 23, 255-257 (1977).
Review:  To say that ``almost all graphs have a given property'' means that if P(n) is the probability that a random graph on n vertices has that property, then P(n) ––> 1 as n ––> oo.It is known that the chromatic index of a simple graph G is either \rho or \rho+1 where \rho is the maximum vertex-degree of G (Vizing's theorem). The second author conjectured that almost all graphs have the chromatic index equal to \rho. The purpose of this paper is to prove the conjecture. The result is deduced from the lemma that almost all graphs have a unique vertex of maximum degree.
Reviewer:  J.Sedlácek
Classif.:  * 05C15 Chromatic theory of graphs and maps

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

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