Cycle Covers in Graphs Without Subdivisions of $K_4$

Abstract

In $[B]$, Bondy conjectured that if $G$ is a $2$-edge-connected simple graph with $n$ vertices, then $G$ admits a cycle cover with at most $(2n-1)/3$ cycles. In this note, we show that if $G$ is a $2$-edge-connected simple graph with $n$ vertices and without subdivisions of $K_4$, then $G$ has a cycle cover with at most $(2n-2)/3$ cycles and we characterize all the extremal graphs. We also show that if $G$ is $2$-edge-connected and has no subdivision of $K_4$, then $G$ is mod $(2k+1)$-orientable for any integer $k\ge 1$.