On the Fine-Grained Complexity of Rainbow Coloring

DOI10.4230/LIPICS.ESA.2016.58zbMath1397.68102arXiv1602.05608OpenAlexW2889201402MaRDI QIDQ4606330

Juho Lauri, Arkadiusz Socała, Łukasz Kowalik

Publication date: 2 March 2018

Full work available at URL: https://arxiv.org/abs/1602.05608

zbMATH Keywords

computational complexitygraph coloringlower boundsexponential time hypothesisFPT algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

On the Fine-Grained Complexity of Rainbow Coloring ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants.

This page was built for publication: On the Fine-Grained Complexity of Rainbow Coloring