# Cyclically 5-edge connected non-bicritical critical snarks

Stefan Grünewald; Eckhard Steffen

Discussiones Mathematicae Graph Theory (1999)

- Volume: 19, Issue: 1, page 5-11
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topStefan Grünewald, and Eckhard Steffen. "Cyclically 5-edge connected non-bicritical critical snarks." Discussiones Mathematicae Graph Theory 19.1 (1999): 5-11. <http://eudml.org/doc/270551>.

@article{StefanGrünewald1999,

abstract = {
Snarks are bridgeless cubic graphs with chromatic index χ' = 4. A snark G is called critical if χ'(G-\{v,w\}) = 3, for any two adjacent vertices v and w.
For any k ≥ 2 we construct cyclically 5-edge connected critical snarks G having an independent set I of at least k vertices such that χ'(G-I) = 4.
For k = 2 this solves a problem of Nedela and Skoviera [6].
},

author = {Stefan Grünewald, Eckhard Steffen},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {cubic graphs; snarks; edge colorings; snark; independent set; edge-chromatic number},

language = {eng},

number = {1},

pages = {5-11},

title = {Cyclically 5-edge connected non-bicritical critical snarks},

url = {http://eudml.org/doc/270551},

volume = {19},

year = {1999},

}

TY - JOUR

AU - Stefan Grünewald

AU - Eckhard Steffen

TI - Cyclically 5-edge connected non-bicritical critical snarks

JO - Discussiones Mathematicae Graph Theory

PY - 1999

VL - 19

IS - 1

SP - 5

EP - 11

AB -
Snarks are bridgeless cubic graphs with chromatic index χ' = 4. A snark G is called critical if χ'(G-{v,w}) = 3, for any two adjacent vertices v and w.
For any k ≥ 2 we construct cyclically 5-edge connected critical snarks G having an independent set I of at least k vertices such that χ'(G-I) = 4.
For k = 2 this solves a problem of Nedela and Skoviera [6].

LA - eng

KW - cubic graphs; snarks; edge colorings; snark; independent set; edge-chromatic number

UR - http://eudml.org/doc/270551

ER -

## References

top- [1] D. Blanusa, Problem ceteriju boja (The problem of four colors), Hrvatsko Prirodoslovno Drustvo Glasnik Math.-Fiz. Astr. Ser. II, 1 (1946) 31-42.
- [2] G. Brinkmann and E. Steffen, Snarks and Reducibility, Ars Combin. 50 (1998) 292-296.
- [3] P.J. Cameron, A.G. Chetwynd and J.J. Watkins, Decomposition of Snarks,J. Graph Theory 11 (1987) 13-19, doi: 10.1002/jgt.3190110104. Zbl0612.05030
- [4] M.K. Goldberg, Construction of class 2 graphs with maximum vertex degree 3, J. Combin. Theory (B) 31 (1981) 282-291, doi: 10.1016/0095-8956(81)90030-7. Zbl0449.05037
- [5] R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221-239, doi: 10.2307/2319844. Zbl0311.05109
- [6] R. Nedela and M. Skoviera, Decompositions and Reductions of Snarks, J. Graph Theory 22 (1996) 253-279, doi: 10.1002/(SICI)1097-0118(199607)22:3<253::AID-JGT6>3.0.CO;2-L Zbl0856.05082
- [7] M. Preissmann, C-minimal Snarks, Annals Discrete Math. 17 (1983) 559-565. Zbl0523.05060
- [8] M. Skoviera, personal communication.
- [9] E. Steffen, Critical Non-bicritical Snarks, Graphs and Combinatorics (to appear). Zbl0939.05071
- [10] E. Steffen, Classifications and Characterizations of Snarks, Discrete Math. 188 (1998) 183-203, doi: 10.1016/S0012-365X(97)00255-0. Zbl0956.05089
- [11] E. Steffen, On bicritical Snarks, Math. Slovaca (to appear). Zbl0985.05022
- [12] J.J. Watkins, Snarks, Ann. New York Acad. Sci. 576 (1989) 606-622, doi: 10.1111/j.1749-6632.1989.tb16441.x.
- [13] J.J. Watkins, R.J. Wilson, A Survey of Snarks, in: Y. Alavi et al. (eds.), Graph Theory, Combinatorics and Applications (Wiley, New York, 1991) 1129-1144. Zbl0841.05035

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.