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

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

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

(36)

• Approximating the orthogonality dimension of graphs and hypergraphs
• Faster 3-coloring of small-diameter graphs
• New tools for graph coloring
• scientific article; zbMATH DE number 7561683 (Why is no real title available?)
• Hardness and algorithms for rainbow connection
• Improved edge-coloring with three colors
• scientific article; zbMATH DE number 1843872 (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
• Heuristics for semirandom graph problems
• Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Matrix relaxations in combinatorial optimization
• Linear index coding via semidefinite programming
• Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
• Intervention efficient algorithms for approximate learning of causal graphs
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Dominating set based exact algorithms for 3-coloring
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Improved Edge-Coloring with Three Colors
• Some recent progress and applications in graph minor theory
• Parameterized and exact algorithms for class domination coloring
• 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
• 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
• Improved linearly ordered colorings of hypergraphs via SDP rounding
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Coloring -colorable graphs using relatively small palettes
• 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)