An O(n^3/14)-coloring algorithm for 3-colorable graphs
DOI10.1016/S0020-0190(96)00190-1zbMATH Open1337.05096OpenAlexW1529433769MaRDI QIDQ290195FDOQ290195
Authors: Avrim Blum, David R. Karger 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Approximate graph coloring by semidefinite programming
- Improved non-approximability results
- Title not available (Why is that?)
- Improving the performance guarantee for approximate graph coloring
- New approximation algorithms for graph coloring
- Ramsey numbers and an approximation algorithm for the vertex cover problem
Cited In (34)
- Faster 3-coloring of small-diameter graphs
- Title not available (Why is that?)
- New tools for graph coloring
- Title not available (Why is that?)
- Deciding 3-colourability in less than O(1.415n) steps
- Hardness and algorithms for rainbow connection
- Improved edge-coloring with three colors
- A simple algorithm for 4-coloring 3-colorable planar graphs
- Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
- Heuristics for semirandom graph problems
- Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
- Linear index coding via semidefinite programming
- Matrix relaxations in combinatorial optimization
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
- Title not available (Why is that?)
- Dominating set based exact algorithms for \(3\)-coloring
- Improved Edge-Coloring with Three Colors
- Parameterized and exact algorithms for class domination coloring
- Some recent progress and applications in graph minor theory
- Parameterized and exact algorithms for class domination coloring
- Semidefinite programming and combinatorial optimization
- On-line coloring \(k\)-colorable graphs
- Robust Factorizations and Colorings of Tensor Graphs
- Approximating \(k\)-forest with resource augmentation: a primal-dual approach
- Title not available (Why is that?)
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
- Convex relaxations and integrality gaps
- Hardness of rainbow coloring hypergraphs
- Coloring -colorable graphs using relatively small palettes
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- Linear index coding via semidefinite programming
- An approximation algorithm for 3-Colourability
This page was built for publication: An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290195)
