2-factors with many cycles

71 Views Asked by At

Petersen's theorem states that every cubic, bridgeless graph contains a perfect matching. Let $G$ be a cubic bridgeless graph, and let $M$ be a perfect matching. Clearly $E(G)-M$ is a 2-factor of $G$ (or, equivalently, $E(G)-M$ induces a subgraph composed of vertex-disjoint cycles covering all vertices of $G$). A graph may have different 2-factors. I'm interested in 2-factors with many cycles. What is known about this? In particular, is there a constant $c$ such that every cubic bridgeless graph with $n$ vertices has a 2-factor with at least $cn$ cycles?

I was able to find results where the goal was to avoid/force cycles of a given size, or to bound the number of cycles from above, but not from below.

1

There are 1 best solutions below

0
On

After putting some effort on the problem and proving that one can find $\Omega(n / \log n)$ cycles of length $O(\log n)$, I got a better feeling of how to search for it in the literature and finally found a paper that proves a slightly more general result:

Brandstädt, Andreas; Voss, Heinz-Jürgen, Short disjoint cycles in graphs with degree constraints, ZBL07784155.