On the chromatic index of almost all graphs (Q1246431): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0095-8956(77)90039-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2150522168 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the edge-chromatic number of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3286850 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4065548 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5538132 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5682013 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5585195 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Almost all Graphs have a Spanning Cycle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multicoloring the incidentors of a weighted directed multigraph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5558480 / rank | |||
Normal rank |
Latest revision as of 23:29, 12 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the chromatic index of almost all graphs |
scientific article |
Statements
On the chromatic index of almost all graphs (English)
0 references
1977
0 references
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)\to 1\) as \(n\to\infty\).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.
0 references