zbMATH — the first resource for mathematics

Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree. (English) Zbl 0704.05041
Let \(G=(V,E)\) be a simple graph and it is said to be Class 1 if the chromatic index equals the maximum degree \(\Delta(G)\). For regular graphs this property means that the edge set is the disjoint union of perfect matchings and such graphs are also called 1-factorizable. The main results of the present paper are three theorems which represent sufficient conditions for simple graphs G to be Class 1 and these conditions essentially depend on the minimum degree \(\delta(G)\) and on the number k(G) of vertices of maximum degree of G. For instance Theorem 1 reads as follows: Let G be a graph of even order 2n; if G satisfies \(\delta(G)\geq n+k(G)-2\), then G is Class 1. The proofs of these main theorems are very extensive ones, and by in part repeated applications of well known lemmas they are based on removing a set of perfect and so- called near-perfect matchings from the graph until the number of vertices of maximum degree is atmost 2. In a further section by application of these theorems three conjectures concerning criticality of a graph respectively its being Class 2 respectively its being Class 1 are proved for special cases and with respect to satisfying certain inequalities for \(\Delta(G)\) and \(k(G)\). They are consequences of a relative general conjecture of Chetwynd and Hilton, if \(\Delta(G)>\frac{1}{3}| V(G)|\) is required, and so results on edge-coloring of these authors are improved.

05C75 Structural characterization of families of graphs
05C35 Extremal problems in graph theory
Full Text: DOI
[1] and , Partial edge-colourings of complete graphs or of graphs which are nearly complete. Graph Theory and Combinatorics, Academic Press, New York (1984) 81–97.
[2] Chetwynd, Proc. London Math. Soc. 50 pp 193– (1985)
[3] Chetwynd, Congr. Numer. 43 pp 221– (1984)
[4] Chetwynd, Graphs Combin. 2 pp 209– (1986)
[5] Chetwynd, Math. Proc. Cambridge Philos. Soc. 100 pp 303– (1986)
[6] Chetwynd, J. Combin. Theory
[7] Chetwynd, J. Graph Theory 7 pp 153– (1983)
[8] de Werra, Rev. Fran. Inf. Rech. Opér. 5 pp 3– (1971)
[9] Dirac, Proc. London Math. Soc. 2 pp 9– (1952)
[10] Hilton, Discrete Math. 64 pp 303– (1987)
[11] Hoffman, J. Combinat. Theory Ser. B 44 pp 372– (1988)
[12] Holyer, SIAM J. Comp. 10 pp 718– (1981)
[13] 1-Faktorisierbarkeit regulärer Graphen hohen Grades. Diplomarbeit, Aachen (1988).
[14] Rosa, Discrete Appl. Math. 4 pp 291– (1982)
[15] Vizing, Diskret. Analiz. 3 pp 25– (1964)
[16] Vizing, Diskret. Analiz. 5 pp 9– (1965)
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.