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

We introduce weak oddness $ω_{\textrm 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$, $ρ(G)\leω_{\textrm w}(G)\leω(G)$, where $ρ(G)$ denotes the resistance of $G$ and $ω(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 $ρ(G) < ω_{\textrm w}(G) < ω(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.

No reviews yet.

No comments yet.