DMGT

Discussiones Mathematicae Graph Theory 19(1) (1999) 5-11
DOI: https://doi.org/10.7151/dmgt.1081

CYCLICALLY 5-EDGE CONNECTED NON-BICRITICAL CRITICAL SNARKS

Stefan Grünewald

Universität Bielefeld, Fakultät für Mathematik
Postfach 100131, 33501 Bielefeld, Germany

Eckhard Steffen

Princeton University
Program in Applied and Computational Mathematics
Fine Hall, Washington Road
Princeton, New Jersey 08544-1000, USA
e-mail: steffen@math.princeton.edu

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

Keywords: cubic graphs, snarks, edge colorings.

1991 Mathematics Subject Classification: 05C15, 05C70.

References

[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.
[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.
[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.
[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.
[7]	M. Preissmann, C-minimal Snarks, Annals Discrete Math. 17 (1983) 559-565.
[8]	M. Skoviera, personal communication.
[9]	E. Steffen, Critical Non-bicritical Snarks, Graphs and Combinatorics (to appear).
[10]	E. Steffen, Classifications and Characterizations of Snarks, Discrete Math. 188 (1998) 183-203, doi: 10.1016/S0012-365X(97)00255-0.
[11]	E. Steffen, On bicritical Snarks, Math. Slovaca (to appear).
[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.

Received 24 November 1997
Revised 21 December 1998