On the complexity of rainbow coloring problems

DOI10.1016/j.dam.2016.10.021zbMath1390.05064arXiv1510.03614OpenAlexW2587480203MaRDI 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

zbMATH Keywords

treewidthgraph algorithmsrainbow connection numberrainbow coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Algorithms for the rainbow vertex coloring problem on graph classes ⋮ On the Fine-Grained Complexity of Rainbow Coloring ⋮ On the complexity of rainbow coloring problems ⋮ The rainbow Steiner tree problem ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes

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