Avoiding 5-Circuits in 2-Factors of Cubic Graphs
Barbora Candráková, Robert Lukoťka · SIAM Journal on Discrete Mathematics · 2015
We show that every 2-edge-connected cubic graph $G$ not isomorphic to the Petersen graph has a 2-factor with at most 2(n-2)/15 circuits of length 5, where $n$ is the number of vertices of $G$. We construct an infinite family of graphs, for which this bound is tight, and improve the bound to n/10 for cyclically 4-edge-connected cubic graphs of girth at least 5. We also show that $G$ has a $2$-factor with at most $n/5.8\overline{3}$ odd circuits.