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