Inapproximability of Rainbow Colouring

DOI10.4230/LIPICS.FSTTCS.2013.153MaRDI QIDQ2963907zbMATH OpenOpenAlexFDO

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

approximation hardnessrainbow colouringrainbow connectivity

Mathematics Subject Classification ID

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

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

(9)

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

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)