Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

DOI10.1137/1.9781611973730.56zbMATH Open1371.68208OpenAlexW2403162531MaRDI QIDQ5363095FDOQ5363095

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

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

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)

Cited In (4)

• The Quest for Strong Inapproximability Results with Perfect Completeness
• Hardness of Rainbow Coloring Hypergraphs
• $(2+\varepsilon)$-Sat Is NP-hard
• 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)