Inapproximability of Rainbow Colouring

DOI10.4230/LIPIcs.FSTTCS.2013.153zbMath1359.68303OpenAlexW1521759172MaRDI QIDQ2963907

Deepak Rajendraprasad, L. Sunil Chandran

Publication date: 21 February 2017

Full work available at URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2013.153

zbMATH Keywords

rainbow connectivityrainbow colouringapproximation hardness

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (8)

On the Fine-Grained Complexity of Rainbow Coloring ⋮ On the complexity of rainbow coloring problems ⋮ Rainbow colouring of split graphs ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Further hardness results on rainbow and strong rainbow connectivity ⋮ 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: Inapproximability of Rainbow Colouring