DIMACS TR: 97-76

Cyclically 5-edge Connected Con-bicritical Critical Snarks

Authors: Stefan Gruenewald and Eckhard Steffen


Snarks are bridgeless cubic graphs with chromatic index $\chi' = 4$. A snark $G$ is called critical if $\chi'(G-\{v,w\}) = 3$, for any two adjacent vertices $v$ and $w$.

For any $k \geq 2$ we construct cyclically 5-edge connected critical snarks $G$ having an independent set $I$ of at least $k$ vertices such that $\chi'(G-I)=4$.

For $k=2$ this solves a problem of Nedela and \v{S}koviera stated in "Decompositions and Reductions of Snarks" J. of Graph Th. 22 253-279 (1996).

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-76.ps.gz

DIMACS Home Page