1-Factorization Conjecture (1985?)

Originator(s): A. G. Chetwynd and A. J. W. Hilton (?)

Conjecture/Question: If G is a 2m-vertex regular graph with degree at least m (when m is odd) or m-1 (when m is even), then G is 1-factorable.

Definitions/Background/motivation: How many rounds are needed to make a mistake in scheduling a round-robin tournament? That is, how many perfect matchings must be deleted from K2m so that the remaining graph cannot be decomposed into perfect matchings? The conjecture states, approximately, that more than half of the edges must be deleted.

Comments/Partial results: The conjecture is implied by the Overfull Conjecture. Partial results involve lowering the value d such that every d-regular graph with n vertices is 1-factorable (assuming n is even). Chetwynd and Hilton showed this for d >= (6/7)n [CH1] and later for d >= (5/6)n [CH2]. The best result is that d >= [(\sqrt7-1)/2]n is sufficient.

more to come

Niessen, Thomas, How to find overfull subgraphs in graphs with large maximum degree. 2nd Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1991). Discrete Appl. Math. 51 (1994), no. 1-2, 117--125. MR 95d:05125 97k:05084 Perkovic, L.; Reed, B. Edge coloring regular graphs of high degree. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 567--578.


Back to Index Page Link to Glossary