Disjoint 1-factors (2012)

Originator: Mike Ferrara    (presented by Jenny Diemunsch - REGS 2012)

Definitions: A $k$-factor of a graph $G$ is a spanning $k$-regular subgraph. Thus a 1-factor of a graph is a perfect matching, and a 2-factor is a spanning 2-regular subgraph, consisting of disjoint cycles that together cover the vertices.

Background: A Hamiltonian cycle in a graph is a 2-factor having one component. Two disjoint perfect matchings in a graph form a spanning union of disjoint even cycles. In a graph of even order, a Hamiltonian cycle decomposes into two disjoint 1-factors. There are sufficient conditions for the existence of a 2-factor. We wish to consider when a graph has a 2-factor with at most $k$ odd components, with specific interest in the case $k=0$. Faudree, Faudree, and Ryjáček [FFR] characterize the pairs of graphs such that forbidding them as induced subgraphs guarantees that a graph has a 2-factor. They are the claw paired with $N(3,1,1)$, $N(4,1,0)$, $N(4,0,0)$, or $P_{7}$, or $K_{1,4}$ paired with $P_{4}$ (see Problem 14).

Question 1: For which of the above pairs does forbidding the two graphs guarantee that a graph with even order has a 2-factor with no odd components?

Comments: Outside an exceptional family, $\{K_{1,4},P_{4}\}$-free graphs with even order graph have a 2-factor with no odd components. Choudum-Paulraj [CP] and Egawa-Ota [EO] showed that every claw-free graph with minimum degree at least 4 has a 2-factor. Yoshimoto [Y] showed that a 2-connected, claw-free graph with minimum degree at least 3 has a 2-factor. Aldred et al. [AEFOS] showed that every 3-edge-connected claw-free graph has a 2-factor.

Question 2: Do there exist $k$ and $\delta_{0}$ such that every $k$-connected claw-free graph of even order and minimum degree at least $\delta_{0}$ has a 2-factor with no odd components?

Comments: A result from Yoshimoto [Y] shows that $\delta_{0} \gt 4$. [DFGM] showed that every $\{K_{1,4}, P_{4}\}$-free graph with even order has a $2$-factor with no odd components or lies in an exceptional family. In REGS discussion, Diemunsch-Ferrara-Morris constructed examples of 3-connected graphs with arbitrarily high minimum degree that do not contain disjoint $1$-factors.

Question 3: Do other properties that guarantee the existence of a 2-factor in a graph also yield a pair of disjoint 1-factors?

References:
[AEFOS] R.E.L. Aldred, Y. Egawa, J. Fujisawa, K. Ota, A. Saito, The existence of a 2-factor in $K_{1,n}$-free graphs with large connectivity and large edge-connectivity, Journal of Graph Theory, 68 (2011), no. 1, 77-89.
[CP] S.A. Choudum, M.S. Paulraj, Regular factors in $K_{1,3}$-free graphs, Journal of Graph Theory, 15 (1991), no. 3, 259-265.
[DFGM] J. Diemunsch, M. Ferrara, S. Graffeo, T. Morris, Guaranteeing disjoint 1-factors in graphs, in preparation.
[EO] Y. Egawa, K. Ota, Regular factors in $K_{1,n}$-free graphs, Journal of Graph Theory, 15 (1991), no. 3, 337-344.
[FFR] J.R. Faudree, R.J. Faudree, and Z. Ryjáček, Forbidden subgraphs that imply 2-factors, Discrete Mathematics, 308 (2008) 1571-1582.
[Y] K. Yoshimoto, On the number of components in 2-factors of claw-free graphs, Discrete Mathematics, 307 (2007), 2808-2819.