An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs

DOI10.1016/S0020-0190(96)00190-1zbMath1337.05096OpenAlexW1529433769MaRDI QIDQ290195

David R. Karger, Avrim L. Blum

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(96)00190-1

zbMATH Keywords

graph coloringanalysis of algorithmsapproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (22)

Matrix Relaxations in Combinatorial Optimization ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Some recent progress and applications in graph minor theory ⋮ Rainbow connections of graphs: a survey ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Hardness and algorithms for rainbow connection ⋮ Linear Index Coding via Semidefinite Programming ⋮ Semidefinite programming and combinatorial optimization ⋮ A simple algorithm for 4-coloring 3-colorable planar graphs ⋮ Unnamed Item ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Convex Relaxations and Integrality Gaps ⋮ On-line coloring \(k\)-colorable graphs ⋮ New Tools for Graph Coloring ⋮ Unnamed Item ⋮ Hardness of Rainbow Coloring Hypergraphs ⋮ Heuristics for semirandom graph problems ⋮ Finding Pseudorandom Colorings of Pseudorandom Graphs

Cites Work

• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Improved non-approximability results
• Improving the performance guarantee for approximate graph coloring
• Approximate graph coloring by semidefinite programming
• New approximation algorithms for graph coloring

This page was built for publication: An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs