Vertex Splitting, Parity Subgraphs and Circuit Covers

Abstract

Let $G$ be a $2$-edge-connected graph and $v$ be a vertex of $G$, and $F\subset F^{\prime }\subset E(v)$ such that $1\le |F|$ and $|F|+2=|F^{\prime }|\le d(v)–1$. Then there is a subset $F^{\ast }$ such that $F\subset F^{\ast }\subset F^{\prime }$ (here, $|F^{\ast }|=|F|+1$), and the graph obtained from $G$ by splitting the edges of $F^{\ast }$ away from $v$ remains $2$-edge-connected unless $v$ is a cut-vertex of $G$. This generalizes a very useful Vertex-Splitting Lemma of Fleischner.
Let $\mathcal{C}$ be a circuit cover of a bridge-less graph $G$. The depth of $\mathcal{C}$ is the smallest integer $k$ such that every vertex of $G$ is contained in at most $k$ circuits of $\mathcal{C}$. It is conjectured by L. Pyber that every bridge-less graph $G$ has a circuit cover $\mathcal{C}$ such that the depth of $\mathcal{C}$ is at most $\mathrm{\Delta }(G)$. In this paper, we prove that

1. every bridge-less graph $G$ has a circuit cover $\mathcal{C}$ such that the depth of $\mathcal{C}$ is at most $\mathrm{\Delta }(G)+2$ and
2. if a bridge-less graph $G$ admits a nowhere-zero $4$-flow or contains no subdivision of the Petersen graph, then $G$ has a circuit cover $\mathcal{C}$ such that the depth of $\mathcal{C}$ is at most $2\lceil 2\mathrm{\Delta }(G)/3\rceil$.