pith. sign in

arxiv: 1602.02949 · v1 · pith:3SPAET44new · submitted 2016-02-09 · 💻 cs.DM · math.CO

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

classification 💻 cs.DM math.CO
keywords oddnessomegacubicgraphsresistancetextrmapproximationarbitrarily
0
0 comments X
read the original abstract

We introduce weak oddness $\omega_{\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$, $\rho(G)\le\omega_{\textrm 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_{\textrm 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.