zbMATH — the first resource for mathematics

The edge-chromatic class of graphs with maximum degree at least \(| V| -3\). (English) Zbl 0692.05032
Graph theory in memory of G. A. Dirac, Pap. Meet., Sandbjerg/Den. 1985, Ann. Discrete Math. 41, 91-110 (1989).
[For the entire collection see Zbl 0656.00008.]
By the famous theorem of V. G. Vizing [Methody Diskret. Anal. 3, 25-30 (1964)] the edge-chromatic number \(\chi'(G)\) of a simple graph G is either the maximum degree \(\Delta(G)\) or \(\Delta(G)+1\). If G contains a subgraph H with \(\Delta (H)=\Delta(G)\) and \(| E(H)| >\Delta(H)\cdot \lfloor | V(G)| /2\rfloor\) then it is easy to see that \(\chi'(G)=\Delta (G)+1.\) For \(\Delta (G)\geq | V(G)| -2\) M. Plantholt [Discrete Math. 47, 91-96 (1983; Zbl 0528.05028)] proved the converse to be true. The present paper extends this to the case \(\Delta (G)\geq | V(G)| -3.\) This is a nontrivial step, but still far from the authors’ general conjecture that the converse is true when \(\Delta(G)>| V(G)| /3.\)
Reviewer: B.Toft

05C15 Coloring of graphs and hypergraphs