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
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
