Petersen cores and the oddness of cubic graphs

Abstract

Let $G$ be a bridgeless cubic graph. Consider a list of $k$ 1-factors of $G$. Let $E_i$ be the set of edges contained in precisely $i$ members of the $k$ 1-factors. Let ${\mu }_k(G)$ be the smallest $|E_0|$ over all lists of $k$ 1-factors of $G$. If $G$ is not 3-edge-colorable, then ${\mu }_3(G)\ge 3$. In [E. Steffen, 1-factor and cycle covers of cubic graphs, J. Graph Theory 78(3) (2015) 195-206] it is shown that if ${\mu }_3(G)\ne 0$, then $2{\mu }_3(G)$ is an upper bound for the girth of $G$. We show that ${\mu }_3(G)$ bounds the oddness $\omega (G)$ of $G$ as well. We prove that $\omega (G)\le \frac{2}{3}{\mu }_3(G)$. If ${\mu }_3(G)=\frac{2}{3}{\mu }_3(G)$, then every ${\mu }_3(G)$-core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4-edge-connected cubic graph $G$ with $\omega (G)=\frac{2}{3}{\mu }_3(G)$. On the other hand, the difference between $\omega (G)$ and $\frac{2}{3}{\mu }_3(G)$ can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer $k\ge 3$, there exists a bridgeless cubic graph $G$ such that ${\mu }_3(G)=k$.

13 pages, 9 figures

References in corpus (3)

• 1-factor and cycle covers of cubic graphs
• On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings
• Intersecting 1-factors and nowhere-zero 5-flows

Cited by in corpus (5)

• An equivalent formulation of the Fan-Raspaud Conjecture and related problems
• On measures of edge-uncolorability of cubic graphs: A brief survey and some new results
• Unions of 1-factors in $r$-graphs and overfull graphs
• Partially normal 5-edge-colorings of cubic graphs
• Cores, joins and the Fano-flow conjectures