Cyclically 5-edge connected non-bicritical critical snarks
Stefan Grünewald, Eckhard Steffen · Discussiones Mathematicae Graph Theory · 1999
Snarks are bridgeless cubic graphs with chromatic index Ø 0 = 4. A snark G is called critical if Ø 0 (G \\Gamma fv; wg) = 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 Ø 0 (G \\Gamma I) = 4. For k = 2 this solves a problem of Nedela and Skoviera [5].