  We introduce a new notion of resilience for constraint satisfaction problems,
with the goal of more precisely determining the boundary between NP-hardness
and the existence of efficient algorithms for resilient instances. In
particular, we study $r$-resiliently $k$-colorable graphs, which are those
$k$-colorable graphs that remain $k$-colorable even after the addition of any
$r$ new edges. We prove lower bounds on the NP-hardness of coloring resiliently
colorable graphs, and provide an algorithm that colors sufficiently resilient
graphs. We also analyze the corresponding notion of resilience for $k$-SAT.
This notion of resilience suggests an array of open questions for graph
coloring and other combinatorial problems.
