Coloring 3-Colorable Graphs with Less than n 1/5 Colors

DOI10.1145/3001582zbMath1426.05166OpenAlexW2600945321MaRDI QIDQ3177885

Ken-ichi Kawarabayashi, Mikkel Thorup

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3001582

zbMATH Keywords

combinatorial algorithm3-colorable graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Topology and Adjunction in Promise Constraint Satisfaction ⋮ Unnamed Item ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Unnamed Item

This page was built for publication: Coloring 3-Colorable Graphs with Less than n ^1/5 Colors