Snarks with resistance n and flow resistance 2n

被引:4
作者
Allie, Imran [1 ]
Macajova, Edita [2 ]
Skoviera, Martin [2 ]
机构
[1] Univ Cape Town, Dept Math & Appl Math, Western Cape, South Africa
[2] Comenius Univ, Dept Comp Sci, Bratislava, Slovakia
关键词
CUBIC GRAPHS; ODDNESS; COVERS;
D O I
10.37236/10633
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We examine the relationship between two measures of uncolourability of cubic graphs - their resistance and flow resistance. The resistance of a cubic graph G, denoted by r(G), is the minimum number of edges whose removal results in a 3-edge-colourable graph. The flow resistance of G, denoted by r(f)(G), is the minimum number of zeroes in a 4-flow on G. Fiol et al. [Electron. J. Combin. 25 (2018), #P4.54] made a conjecture that r(f)(G) <= r(G) for every cubic graph G. We disprove this conjecture by presenting a family of cubic graphs G(n) of order 34n, where n >= 3, with resistance n and flow resistance 2n. For n >= 5 these graphs are nontrivial snarks.
引用
收藏
页数:10
相关论文
共 16 条
[1]   Oddness to resistance ratios in cubic graphs [J].
Allie, I .
DISCRETE MATHEMATICS, 2019, 342 (02) :387-392
[2]   Generation and properties of snarks [J].
Brinkmann, Gunnar ;
Goedgebeur, Jan ;
Hagglund, Jonas ;
Markstrom, Klas .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (04) :468-488
[3]   3-Flows with large support [J].
DeVos, Matt ;
McDonald, Jessica ;
Pivotto, Irene ;
Rollova, Edita ;
Samal, Robert .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 144 :32-80
[4]  
Fiol MA, 2018, ELECTRON J COMB, V25
[5]  
Fulkerson D. R, 1971, Mathematical Programming, V1, P16
[6]   Double covers of cubic graphs with oddness 4 [J].
Häggkvist, R ;
McGuinness, S .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 93 (02) :251-277
[7]  
JAEGER F, 1985, ARS COMBINATORIA, V20B, P229
[8]  
Jaeger F, 1985, North-Holland Mathematics Studies, V27, P1, DOI DOI 10.1016/S0304-0208(08)72993-1
[9]  
Kaiser T., 2006, Topics in Discrete Mathematics, V26, P225, DOI [10.1007/3-540-33700-8_14, DOI 10.1007/3-540-33700-8_14]
[10]   Sparsely intersecting perfect matchings in cubic graphs [J].
Macajova, Edita ;
Skoviera, Martin .
COMBINATORICA, 2014, 34 (01) :61-94