On the complexity of rainbow coloring problems
From MaRDI portal
Publication:1647834
DOI10.1016/j.dam.2016.10.021zbMath1390.05064arXiv1510.03614MaRDI QIDQ1647834
Juho Lauri, Eduard Eiben, Robert Ganian
Publication date: 27 June 2018
Published in: Discrete Applied Mathematics, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1510.03614
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes, A survey on rainbow (vertex-)index of graphs, Complexity of rainbow vertex connectivity problems for restricted graph classes, Algorithms for the rainbow vertex coloring problem on graph classes, On the complexity of rainbow coloring problems, The rainbow Steiner tree problem, On the Fine-Grained Complexity of Rainbow Coloring
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Fundamentals of parameterized complexity
- Further hardness results on the rainbow vertex-connection number of graphs
- Hardness and algorithms for rainbow connection
- The complexity of determining the rainbow vertex-connection of a graph
- Further hardness results on rainbow and strong rainbow connectivity
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- On the complexity of rainbow coloring problems
- Rainbow connections of graphs: a survey
- Linear time solvable optimization problems on graphs of bounded clique-width
- A logical approach to multicut problems
- On the corona of two graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Rainbow connection number and connected dominating sets
- New Hardness Results in Rainbow Connectivity
- Rainbow Colouring of Split and Threshold Graphs
- Inapproximability of Rainbow Colouring
- Rainbow trees in graphs and generalized connectivity
- Rainbow connection in graphs
- Graph minors. II. Algorithmic aspects of tree-width
- On Linear Time Minor Tests with Depth-First Search
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- The rainbow connection of a graph is (at most) reciprocal to its minimum degree
- The strong rainbow vertex-connection of graphs