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

MSC:
 05C15 Coloring of graphs and hypergraphs
Keywords:
edge-chromatic number