This is the authors' abstract. We don't add key points for this paper.
We call a (not necessarily properly) edge-colored graph edge-color-avoiding connected if after the removal of edges of any single color, the graph remains connected. For vertex-colored graphs, similar definitions of color-avoiding connectivity can be given. In this article, we investigate the problem of determining the maximum number of edges that can be removed from either an edge- or a vertex-colored, color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, and then, we give a polynomial-time approximation algorithm for it. To analyze the approximation factor of this algorithm, we determine the minimum number of edges of color-avoiding connected graphs on a given number of vertices and with a given number of colors. Furthermore, we also consider a generalization of edge-color-avoiding connectivity to matroids.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Pintér et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: