Hardness and algorithms for rainbow connection
From MaRDI portal
Publication:491198
DOI10.1007/s10878-009-9250-9zbMath1319.05049arXiv0809.2493OpenAlexW2150438015MaRDI QIDQ491198
Eldar Fischer, Sourav Chakraborty, Arie Matsliah, Raphael Yuster
Publication date: 24 August 2015
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0809.2493
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)
Related Items (69)
The 3-rainbow index and connected dominating sets ⋮ On finding rainbow and colorful paths ⋮ Hardness results for total 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 ⋮ Upper bounding rainbow connection number by forest number ⋮ The rainbow connection number of the power graph of a finite group ⋮ Rainbow Connection of Random Regular Graphs ⋮ On the Fine-Grained Complexity of Rainbow Coloring ⋮ Rainbow connection number of comb product of graphs ⋮ Rainbow connection number of amalgamation of some graphs ⋮ Some remarks on rainbow connectivity ⋮ Upper bounds for the total rainbow connection of graphs ⋮ On the complexity of rainbow coloring problems ⋮ More on the rainbow disconnection in graphs ⋮ Rainbow connection number and independence number of a graph ⋮ Rainbow colouring of split graphs ⋮ Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number ⋮ Rainbow connection number and graph operations ⋮ Rainbow antistrong connection in tournaments ⋮ The strong 3-rainbow index of edge-comb product of a path and a connected graph ⋮ Rainbow connection in 3-connected graphs ⋮ On the rainbow connectivity of graphs: complexity and FPT algorithms ⋮ The strong 3-rainbow index of some certain graphs and its amalgamation ⋮ Rainbow connection numbers of Cayley graphs ⋮ The rainbow connection number of 2-connected graphs ⋮ Further hardness results on the rainbow vertex-connection number of graphs ⋮ The rainbow Steiner tree problem ⋮ (Strong) rainbow connection on the splitting of 3-path ⋮ An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs ⋮ (1, 2)-rainbow connection number at most 3 in connected dense graphs ⋮ Rainbow connection of graphs with diameter 2 ⋮ On the complexity of \(k\)-rainbow cycle colouring problems ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Loose edge-connection of graphs ⋮ On 3-degree 4-chordal graphs ⋮ Strong rainbow connection in digraphs ⋮ Hardness results for three kinds of colored connections of graphs ⋮ Further hardness results on rainbow and strong rainbow connectivity ⋮ Rainbow connection in oriented graphs ⋮ The vertex-rainbow connection number of some graph operations ⋮ On forbidden subgraphs and rainbow connection in graphs with minimum degree 2 ⋮ Hardness result for the total rainbow \(k\)-connection of graphs ⋮ Rainbow connection number of graph power and graph products ⋮ Rainbow connection number and the number of blocks ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Rainbow connection numbers of Cayley digraphs on abelian groups ⋮ On total rainbow \(k\)-connected graphs ⋮ Generalized rainbow connection of graphs ⋮ Rainbow connection in some digraphs ⋮ Rainbow connection number of graphs with diameter 3 ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ On the complexity of generalized chromatic polynomials ⋮ Rainbow connections in digraphs ⋮ Rainbow connection and graph products ⋮ Conflict-free connection number and independence number of a graph ⋮ Rainbow \(k\)-connectivity of random bipartite graphs ⋮ (Strong) conflict-free connectivity: algorithm and complexity ⋮ The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths ⋮ On the (di)graphs with (directed) proper connection number two ⋮ On the (di)graphs with (directed) proper connection number two ⋮ Generalized rainbow connectivity of graphs ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants. ⋮ Rainbow and monochromatic vertex-connection of random graphs ⋮ Rainbow connectivity and rainbow criticality on graph classes ⋮ Rainbow perfect domination in lattice graphs ⋮ Rainbow connection and forbidden subgraphs
Cites Work
This page was built for publication: Hardness and algorithms for rainbow connection
