zbMATH — the first resource for mathematics

1-factorizing regular graphs of high degree - an improved bound. (English) Zbl 0675.05030
The authors improve their previous results concerning 1-factorization of regular graphs of even order. Let G be a regular graph of even order and degree d(G). In their paper “Regular graphs of high degree are 1- factorizable”, Proc. Lond. Math. Soc., III. Ser. 50, 193-206 (1985; Zbl 0561.05027) the authors proved that if d(G)\(\geq (6/7)| V(G)|\) the G has a 1-factorization. In this paper they improve the bound to d(G)\(\geq (\sqrt{7}-1)| V(G)|\) which is slightly better than (5/6)\(| V(G)|\).
Reviewer: A.Hartman

05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] Chetwynd, A.G.; Hilton, A.J.W., Regular graphs of high degree are 1-factorizable, Proc. London math. soc., 50, 3, 193-206, (1985) · Zbl 0561.05027
[2] Chetwynd, A.G.; Hilton, A.J.W., A δ-subgraph condition for a graph to be class 1, J. combinat. theory (B), 46, 37-45, (1989) · Zbl 0611.05025
[3] A.G. Chetwynd, A.J.W. Hilton and D.G. Hoffman, On the Δ-subgraph of graphs which are critical with respect to the chromatic index, J. Combinat. Theory (B), to appear. · Zbl 0626.05028
[4] Dirac, G.A., Some theorems on abstract graphs, Proc. London math. soc., 2, 3, 69-81, (1952) · Zbl 0047.17001
[5] Fournier, J.-C., Colorations des arêtes d’un graphe, Cahiers de CERO, 15, 311-314, (1973) · Zbl 0273.05109
[6] Hoffman, D.G.; Rodger, C.A., Class one graphs, J. combinat. theory (B), 44, 372-376, (1988) · Zbl 0659.05071
[7] Vizing, V.G., On an estimate of the chromatic class of a p-graph, Diskret. analiz., 3, 25-30, (1964), (in 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.