首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Oddness to resistance ratios in cubic graphs
Authors:I Allie
Abstract:Let G be a bridgeless cubic graph. Oddness (weak oddness) is defined as the minimum number of odd components in a 2-factor (an even factor) of G, denoted as ω(G) (Steffen, 2004) (ω(G) Lukot’ka and Mazák (2016)). Oddness and weak oddness have been referred to as measurements of uncolourability (Fiol et al., 2017, Lukot’ka and Mazák, 2016, Lukot’ka et al., 2015 and, Steffen, 2004), due to the fact that ω(G)=0 and ω(G)=0 if and only if G is 3-edge-colourable. Another so-called measurement of uncolourability is resistance, defined as the minimum number of edges that can be removed from G such that the resulting graph is 3-edge-colourable, denoted as r(G) (Steffen, 2004). It is easily shown that ω(G)ω(G)r(G). While it has been shown that the difference between any two of these measures can be arbitrarily large, it has been conjectured that ω(G)2r(G), and that if G is a snark then ω(G)2r(G) (Fiol et al., 2017). In this paper, we disprove the latter by showing that the ratio of oddness to weak oddness can be arbitrarily large. We also offer some insights into the former conjecture by defining what we call resistance reducibility, and hypothesizing that almost all cubic graphs are such resistance reducible.
Keywords:Cubic graphs  Snark  Oddness  Weak oddness  Resistance
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号