On the Hardness of 4-Coloring a 3-Colorable Graph
From MaRDI portal
Publication:4652619
DOI10.1137/S0895480100376794zbMath1087.68071MaRDI QIDQ4652619
Sanjeev Khanna, Venkatesan Guruswami
Publication date: 28 February 2005
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Unnamed Item ⋮ A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring ⋮ Unnamed Item ⋮ Dominating set based exact algorithms for \(3\)-coloring ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Constructive generation of very hard 3-colorability instances ⋮ Linear Index Coding via Semidefinite Programming ⋮ Unnamed Item ⋮ Hypergraph list coloring and Euclidean Ramsey theory ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Unnamed Item ⋮ Hardness of Rainbow Coloring Hypergraphs
