## DIMACS TR: 97-76

## Cyclically 5-edge Connected Con-bicritical Critical Snarks

### Authors: Stefan Gruenewald and Eckhard Steffen

**
ABSTRACT
**

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