$k$-Cycle Free One-Factorizations of Complete Graphs

Mariusz Meszka


It is proved that for every $n\geq 3$ and every even $k\geq 4$, where $k\neq 2n$, there exists one-factorization of the complete graph $K_{2n}$ such that any two one-factors do not induce a graph with a cycle of length $k$ as a component. Moreover, some infinite classes of one-factorizations, in which lengths of cycles induced by any two one-factors satisfy a given lower bound, are constructed.

Full Text: PDF