A still better performance guarantee for approximate graph coloring

1993/01/01 by Magnús M. Halldórsson · 5 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Graph #Graph coloring #Graph power #Greedy coloring #Line graph #Parallel computing #Theoretical computer science

paper · doi:10.1016/0020-0190(93)90246-6

crossref issued 1993/01/01 · crossref published 1993/01/01 · crossref published-print 1993/01/01 · openalex publication_date 1993/01/01 · crossref created 2002/07/26 · crossref deposited 2019/04/13 · openalex created_date 2025/10/10 · crossref indexed 2026/02/27 · openalex updated_date 2026/07/23

Citations

• On the hardness of approximating minimization problems
• Approximating maximum independent sets by excluding subgraphs

Cited by

• All Structured Programs Have Small Tree Width and Good Register Allocation
• Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm
• Approximating clique is almost NP-complete
• Approximate graph coloring by semidefinite programming
• Graph coloring [wikipedia]