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

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI
[1] 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
[2] Chetwynd, A.G; Hilton, A.J.W, Regular graphs of high degree are 1-factorizable, (), 193-206 · Zbl 0561.05027
[3] 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
[4] Dirac, G.A, Some theorems on abstract graphs, (), 69-81 · Zbl 0047.17001
[5] Fiorini, S; Wilson, R.J, Edge-colourings of graphs, (), No. 16 · Zbl 0421.05023
[6] 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
[7] Holyer, I, The NP-completeness of edge-coloring, SIAM J. comp., 10, 718-720, (1981) · Zbl 0473.68034
[8] König, D, Theorie der endlichen und unendlichen graphen, (1950), Chelsea, New York · Zbl 0040.10303
[9] 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.