Geodesic
Snarks with resistance \(n\) and flow resistance \(2n\)
Imran Allie1 ; Edita Máčajová2 ; Martin Škoviera2
1University of Cape Town
2Comenius University
The electronic journal of combinatorics, Tome 29 (2022) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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) \leq 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 \geq 3$, with resistance $n$ and flow resistance $2n$. For $n\ge 5$ these graphs are nontrivial snarks.
DOI : 10.37236/10633
Classification : 05C15, 05C35, 05C21
Mots-clés : resistance of a cubic graph, Tait coloring, snark, Boole coloring, Berge's conjecture, Tutte's 5-flow conjecture

Imran Allie  1   ; Edita Máčajová  2   ; Martin Škoviera  2

1 University of Cape Town
2 Comenius University 
@article{10_37236_10633,
     author = {Imran Allie and Edita M\'a\v{c}ajov\'a and Martin \v{S}koviera},
     title = {Snarks with resistance \(n\) and flow resistance \(2n\)},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {1},
     doi = {10.37236/10633},
     zbl = {1486.05080},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10633/}
}
TY  - JOUR
AU  - Imran Allie
AU  - Edita Máčajová
AU  - Martin Škoviera
TI  - Snarks with resistance \(n\) and flow resistance \(2n\)
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10633/
DO  - 10.37236/10633
ID  - 10_37236_10633
ER  - 
%0 Journal Article
%A Imran Allie
%A Edita Máčajová
%A Martin Škoviera
%T Snarks with resistance \(n\) and flow resistance \(2n\)
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10633/
%R 10.37236/10633
%F 10_37236_10633
Imran Allie; Edita Máčajová; Martin Škoviera. Snarks with resistance \(n\) and flow resistance \(2n\). The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10633

Cité par Sources :