Weak oddness as an approximation of oddness and resistance in cubic graphs

Abstract

We introduce weak oddness ${\omega }_{\text{w}}$, a new measure of uncolourability of cubic graphs, defined as the least number of odd components in an even factor. For every bridgeless cubic graph $G$, $\rho (G)\le {\omega }_{\text{w}}(G)\le \omega (G)$, where $\rho (G)$ denotes the resistance of $G$ and $\omega (G)$ denotes the oddness of $G$, so this new measure is an approximation of both oddness and resistance. We demonstrate that there are graphs $G$ satisfying $\rho (G)<{\omega }_{\text{w}}(G)<\omega (G)$, and that the difference between any two of those three measures can be arbitrarily large. The construction implies that if we replace a vertex of a cubic graph with a triangle, then its oddness can decrease by an arbitrarily large amount.