On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors

DOI10.1007/978-3-642-15369-3_11zbMath1304.68060OpenAlexW1539723571MaRDI QIDQ3588404

Irit Dinur, Igor Shinkar

Publication date: 10 September 2010

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15369-3_11

zbMATH Keywords

graph coloringhardness of approximationmajority is stablest

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Topology and Adjunction in Promise Constraint Satisfaction ⋮ Unnamed Item ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Unnamed Item ⋮ On percolation and ‐hardness ⋮ Kneser graphs are like Swiss cheese ⋮ Unnamed Item

This page was built for publication: On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors