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

Abstract

top
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].

How to cite

top

Stefan 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. [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. [2] G. Brinkmann and E. Steffen, Snarks and Reducibility, Ars Combin. 50 (1998) 292-296. 
  3. [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. [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. [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. [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. [7] M. Preissmann, C-minimal Snarks, Annals Discrete Math. 17 (1983) 559-565. Zbl0523.05060
  8. [8] M. Skoviera, personal communication. 
  9. [9] E. Steffen, Critical Non-bicritical Snarks, Graphs and Combinatorics (to appear). Zbl0939.05071
  10. [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. [11] E. Steffen, On bicritical Snarks, Math. Slovaca (to appear). Zbl0985.05022
  12. [12] J.J. Watkins, Snarks, Ann. New York Acad. Sci. 576 (1989) 606-622, doi: 10.1111/j.1749-6632.1989.tb16441.x. 
  13. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.