Geodesic
On snarks that are far from being 3-edge colorable
Jonas Hägglund1
1Umeå University
The electronic journal of combinatorics, Tome 23 (2016) no. 2

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv
In this note we construct two infinite snark families which have high oddness and low circumference compared to the number of vertices. Using this construction, we also give a counterexample to a suggested strengthening of Fulkerson's conjecture by showing that the Petersen graph is not the only cyclically 4-edge connected cubic graph which require at least five perfect matchings to cover its edges. Furthermore the counterexample presented has the interesting property that no 2-factor can be part of a cycle double cover.
DOI : 10.37236/3430
Classification : 05C15, 05C70, 05C38
Mots-clés : snarks, perfect matching covers, oddness, uncolorability measures

Jonas Hägglund  1

1 Umeå University 
Jonas Hägglund. On snarks that are far from being 3-edge colorable. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/3430
@article{10_37236_3430,
     author = {Jonas H\"agglund},
     title = {On snarks that are far from being 3-edge colorable},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {2},
     doi = {10.37236/3430},
     zbl = {1335.05064},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3430/}
}
TY  - JOUR
AU  - Jonas Hägglund
TI  - On snarks that are far from being 3-edge colorable
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3430/
DO  - 10.37236/3430
ID  - 10_37236_3430
ER  - 
%0 Journal Article
%A Jonas Hägglund
%T On snarks that are far from being 3-edge colorable
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3430/
%R 10.37236/3430
%F 10_37236_3430

Cité par Sources :