Inapproximability of Rainbow Colouring

DOI10.4230/LIPICS.FSTTCS.2013.153MaRDI QIDQ2963907zbMATHOpenAlexFDO

Authors L. Sunil Chandran, Deepak Rajendraprasad

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

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

Recommendations

• Improved Inapproximability of Rainbow Coloring
• On the fine-grained complexity of rainbow coloring
• On the fine-grained complexity of rainbow coloring
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• Rainbow coloring hardness via low sensitivity polymorphisms
• Fine-grained complexity of rainbow coloring and its variants
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• Algorithms and bounds for very strong rainbow coloring

Cited in

(8)

• Fine-grained complexity of rainbow coloring and its variants
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• Rainbow connection number and radius
• Rainbow colouring of split graphs
• Further hardness results on rainbow and strong rainbow connectivity
• On the fine-grained complexity of rainbow coloring
• Rainbow vertex coloring bipartite graphs and chordal graphs
• A survey on rainbow (vertex-)index of graphs

This page was built for publication: Inapproximability of Rainbow Colouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963907)