# zbMATH — the first resource for mathematics

The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small. (English) Zbl 0716.05021
Let h(G) denote the maximum vertex degree of a simple graph G. By Vizing’s theorem, the chromatic index $$\chi '(G)$$ of G is at most $$h(G)+1$$. Graphs for which $$\chi '(G)=h(G)$$ are said to be class 1, and otherwise they are class 2. There is described the structure of graphs with class 1 and class 2 respectively. Gained results provide quite strong evidence for the following conjecture. We put $$t(G)=\max_{H}\lceil 2| E(H)| /| V(H)| -1\rceil$$, where the maximum is taken over all subgraphs H of G of odd order. Let $$f(G)=\max \{h(G),t(G)\}$$. Conjecture. If h(G)$$\geq | V(G)|$$, then $$\chi '(G)=f(G)$$.
Reviewer: J.Fiamčík

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory
Full Text:
##### References:
  Chetwynd, A.G; Hilton, A.J.W, Partial edge-colourings of complete graphs or of graphs which are nearly complete, (), 81-97 · Zbl 0549.05027  Chetwynd, A.G; Hilton, A.J.W, Regular graphs of high degree are 1-factorizable, (), 193-206 · Zbl 0561.05027  Chetwynd, A.G; Hilton, A.J.W, The chromatic index of graphs with at most four vertices of maximum degree, (), 221-248 · Zbl 0561.05023  Dirac, G.A, Some theorems on abstract graphs, (), 69-81 · Zbl 0047.17001  Fiorini, S; Wilson, R.J, Edge-colourings of graphs, (), No. 16 · Zbl 0421.05023  Fournier, J.-C, Méthode et théorème générale de coloration des arêtes, J. math. pures appl., 56, 437-453, (1977) · Zbl 0326.05103  Holyer, I, The NP-completeness of edge-coloring, SIAM J. comp., 10, 718-720, (1981) · Zbl 0473.68034  König, D, Theorie der endlichen und unendlichen graphen, (1950), Chelsea, New York · Zbl 0040.10303  Vizing, V.G, On an estimate of the chromatic class of a p-graph, Disket. analiz., 3, 25-30, (1964), [Russian]
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.