A one-factorization of a finite simple graph is a set partition of its edge set into perfect matchings, also called 1-factors (Wallis 1997; Gill and Wanless 2020, p. 177). Each graph vertex is incident to exactly one graph edge in each factor. Thus a graph with a graph edge and a one-factorization is regular. For an -regular graph with , a one-factorization is equivalent to a proper coloring of its edges with colors.

For example, the complete graph on vertices 1, 2, 3, and 4 has the three factors , , and , where denotes the graph edge joining and . The union of any two of these factors is a Hamiltonian cycle, so this is also a perfect one-factorization.

See also

Edge Coloring, Graph Factor, Perfect Matching, Perfect One-Factorization

Explore with Wolfram|Alpha

References

Gill, M. J. and Wanless, I. M. "Perfect 1-Factorisations of ." Bull. Austral. Math. Soc. 101, 177-185, 2020. https://doi.org/10.1017/S0004972719000856.Wallis, W. D. One-Factorizations. Dordrecht, Netherlands: Kluwer, 1997. https://doi.org/10.1007/978-1-4757-2564-3.

Cite this as:

Weisstein, Eric W. "One-Factorization." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/One-Factorization.html

Subject classifications