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