On the complexity of rainbow coloring problems

DOI10.1016/j.dam.2016.10.021zbMath1390.05064arXiv1510.03614MaRDI QIDQ1647834

Juho Lauri, Robert Ganian, Eduard Eiben

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

treewidth; graph algorithms; rainbow connection number; rainbow coloring

Mathematics Subject Classification ID

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)