Strong inapproximability results on balanced rainbow-colorable hypergraphs

DOI10.1007/S00493-016-3383-0zbMath1424.05087OpenAlexW2775735346MaRDI QIDQ1715058

Venkatesan Guruswami, Euiwoong Lee

Publication date: 1 February 2019

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-016-3383-0

zbMATH Keywords

hypergraph$K$-uniform hyperhraphrainbow $k$-coloring

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Topology and Adjunction in Promise Constraint Satisfaction ⋮ A Characterization of hard-to-cover CSPs ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms

This page was built for publication: Strong inapproximability results on balanced rainbow-colorable hypergraphs