Avoiding 7-Circuits in 2-Factors of Cubic Graphs

Abstract

Let $G$ be a cyclically $4$-edge-connected cubic graph with girth at least $7$ on $n$ vertices. We show that $G$ has a $2$-factor $F$ such that at least a linear amount of vertices is not in $7$-circuits of $F$. More precisely, there are at least $n/657$ vertices of $G$ that are not in $7$-circuits of $F$. If $G$ is cyclically $6$-edge-connected then the bound can be improved to $n/189$. As a corollary we obtain bounds on the oddness and on the length of the shortest travelling salesman tour in a cyclically $4$-edge-connected ($6$-edge-connected) cubic graph of girth at least $7$.