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 条
[11]  
Schrijver A, 2003, COMPINATORIAL OPTIMI
[12]  
Seymour P., 1979, GRAPH THEORY RELATED, P342
[13]   Measurements of edge-uncolorability [J].
Steffen, E .
DISCRETE MATHEMATICS, 2004, 280 (1-3) :191-214
[14]   Classifications and characterizations of snarks [J].
Steffen, E .
DISCRETE MATHEMATICS, 1998, 188 (1-3) :183-203
[15]   1-Factor and Cycle Covers of Cubic Graphs [J].
Steffen, Eckhard .
JOURNAL OF GRAPH THEORY, 2015, 78 (03) :195-206
[16]   A CONTRIBUTION TO THE THEORY OF CHROMATIC POLYNOMIALS [J].
TUTTE, WT .
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1954, 6 (01) :80-91