Hardness and algorithms for rainbow connection
From MaRDI portal
Abstract: An edge-colored graph is {em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {em rainbow connection} of a connected graph , denoted , is the smallest number of colors that are needed in order to make rainbow connected. In the first result of this paper we prove that computing is NP-Hard solving an open problem from cite{Ca-Yu}. In fact, we prove that it is already NP-Complete to decide if , and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every , a connected graph with minimum degree at least has {em bounded} rainbow connection, where the bound depends only on , and a corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.
Recommendations
Cites work
Cited in
(76)- The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths
- The rainbow Steiner tree problem
- Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph
- On 3-degree 4-chordal graphs
- Upper bounding rainbow connection number by forest number
- An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs
- The strong 3-rainbow index of edge-comb product of a path and a connected graph
- (1, 2)-rainbow connection number at most 3 in connected dense graphs
- Rainbow antistrong connection in tournaments
- (Strong) rainbow connection on the splitting of 3-path
- Counting on rainbow \(k\)-connections
- A survey on rainbow (vertex-)index of graphs
- Color-avoiding connected spanning subgraphs with minimum number of edges
- Rainbow connection number of corona product of graphs
- Rainbow connectivity and rainbow criticality on graph classes
- Fine-grained complexity of rainbow coloring and its variants
- Fine-Grained Complexity of Rainbow Coloring and its Variants.
- On total rainbow \(k\)-connected graphs
- Loose edge-connection of graphs
- The vertex-rainbow connection number of some graph operations
- Rainbow connection and graph products
- Rainbow connection number of graphs with diameter 3
- Hardness results for total rainbow connection of graphs
- Rainbow connection number and graph operations
- Rainbow connection number and independence number of a graph
- (Strong) conflict-free connectivity: algorithm and complexity
- Rainbow colouring of split graphs
- Rainbow connectivity: hardness and tractability
- Rainbow connections for outerplanar graphs with diameter 2 and 3
- Rainbow connection number of graph power and graph products
- Rainbow connection of graphs with diameter 2
- Hardness and Algorithms for Rainbow Connectivity
- Strong rainbow connection in digraphs
- More on the rainbow disconnection in graphs
- Rainbow and monochromatic vertex-connection of random graphs
- Rainbow perfect domination in lattice graphs
- Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
- Hardness results for three kinds of colored connections of graphs
- Rainbow connection and forbidden subgraphs
- Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs
- On the complexity of \(k\)-rainbow cycle colouring problems
- On the complexity of generalized chromatic polynomials
- Generalized rainbow connectivity of graphs
- Rainbow \(k\)-connectivity of random bipartite graphs
- Rainbow connection number and the number of blocks
- The rainbow connection number of 2-connected graphs
- Further hardness results on the rainbow vertex-connection number of graphs
- Further hardness results on rainbow and strong rainbow connectivity
- The strong 3-rainbow index of some certain graphs and its amalgamation
- The rainbow connection number of the power graph of a finite group
- On the fine-grained complexity of rainbow coloring
- Rainbow connection number of comb product of graphs
- Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number
- Rainbow vertex coloring bipartite graphs and chordal graphs
- Rainbow connection of random regular graphs
- Rainbow connections in digraphs
- On the (di)graphs with (directed) proper connection number two
- Rainbow connection number of amalgamation of some graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Upper bounds for the total rainbow connection of graphs
- On forbidden subgraphs and rainbow connection in graphs with minimum degree 2
- Hardness result for the total rainbow \(k\)-connection of graphs
- Rainbow connection numbers of Cayley graphs
- Rainbow connection in some digraphs
- Complexity of rainbow vertex connectivity problems for restricted graph classes
- Rainbow connection numbers of Cayley digraphs on abelian groups
- Rainbow connection in 3-connected graphs
- On finding rainbow and colorful paths
- The 3-rainbow index and connected dominating sets
- Conflict-free connection number and independence number of a graph
- Generalized rainbow connection of graphs
- Finite families of forbidden subgraphs for rainbow connection in graphs
- Note on the upper bound of the rainbow index of a graph
- Sufficient conditions for 2-rainbow connected graphs
- On the (di)graphs with (directed) proper connection number two
- Rainbow connection in oriented graphs
This page was built for publication: Hardness and algorithms for rainbow connection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491198)
