Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

DOI10.1137/1.9781611973730.56MaRDI QIDQ5363095zbMATHOpenAlexFDO

Authors Euiwoong Lee, Venkatesan Guruswami

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.56

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Recommendations

• Strong inapproximability results on balanced rainbow-colorable hypergraphs
• On balanced colorings of hypergraphs
• On balanced colorings of sparse hypergraphs
• Good and nice colorings of balanced hypergraphs
• On rainbow-free colourings of uniform hypergraphs
• Large rainbow matchings in semi-strong edge-colorings of graphs
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Rainbow domination and related problems on strongly chordal graphs
• A note on rainbow matchings in strongly edge-colored graphs
• Strong colourings of hypergraphs

Cited in

(8)

• Hardness of rainbow coloring hypergraphs
• \((2+\varepsilon)\)-Sat is NP-hard
• Approximate hypergraph coloring under low-discrepancy and related promises
• Rainbow coloring hardness via low sensitivity polymorphisms
• The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number
• Strong inapproximability results on balanced rainbow-colorable hypergraphs
• The quest for strong inapproximability results with perfect completeness
• NP-completeness results for partitioning a graph into total dominating sets

This page was built for publication: Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

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