We study network robustness under correlated failures modeled by colors, where each color represents a class of edges or vertices that may fail simultaneously. An edge-colored graph is said to be edge-color-avoiding k-edge-connected if it remains k-edge-connected after the removal of all edges of any single color. We characterize the graphs that admit such a coloring and show that, when k = 1, one can determine in polynomial time both the minimum number of colors required and a coloring achieving it; while the problem becomes NP-hard for k 2. We also investigate the problem of orienting the edges of a graph so that the resulting digraph remains strongly or rooted connected even after the removal of all arcs of any single color. In addition, we explore generalizations involving vertex-colorings, k-vertex-connectivity, simultaneous failures of multiple colors and matroids.
Pintér et al. (Fri,) studied this question.