An O(n^3/14)-coloring algorithm for 3-colorable graphs

DOI10.1016/S0020-0190(96)00190-1MaRDI QIDQ290195zbMATHOpenAlexFDO

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

zbMATH Keywords

analysis of algorithmsapproximation algorithmsgraph coloring

Mathematics Subject Classification ID

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

Recommendations

• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Coloring \(k\)-colorable graphs using smaller palettes
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Coloring -colorable graphs using relatively small palettes
• On-line coloring \(k\)-colorable graphs

Cites work

• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• Approximate graph coloring by semidefinite programming
• Improved non-approximability results
• 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)

• Dominating set based exact algorithms for \(3\)-coloring
• Hardness of rainbow coloring hypergraphs
• Parameterized and exact algorithms for class domination coloring
• Linear index coding via semidefinite programming
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• scientific article; zbMATH DE number 1843872 (Why is no real title available?)
• Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
• Semidefinite programming and combinatorial optimization
• scientific article; zbMATH DE number 7561683 (Why is no real title available?)
• Deciding 3-colourability in less than O(1.415n) steps
• A simple algorithm for 4-coloring 3-colorable planar graphs
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• On-line coloring \(k\)-colorable graphs
• Some recent progress and applications in graph minor theory
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• Linear index coding via semidefinite programming
• Improved Edge-Coloring with Three Colors
• Parameterized and exact algorithms for class domination coloring
• Faster 3-coloring of small-diameter graphs
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• New tools for graph coloring
• Approximating the orthogonality dimension of graphs and hypergraphs
• Robust Factorizations and Colorings of Tensor Graphs
• Hardness and algorithms for rainbow connection
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Coloring -colorable graphs using relatively small palettes
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Matrix relaxations in combinatorial optimization
• Convex relaxations and integrality gaps
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
• Heuristics for semirandom graph problems
• An approximation algorithm for 3-Colourability
• Improved edge-coloring with three colors

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)