**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
*K _{2m}* 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

**References:**

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.

**Keywords:**