An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
From MaRDI portal
Publication:290195
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
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
This page was built for publication: An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
