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

• 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

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)

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 (29)

• Convex Relaxations and Integrality Gaps
• 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
• Heuristics for semirandom graph problems
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Hardness of Rainbow Coloring Hypergraphs
• Title not available (Why is that?)
• Rainbow connections of graphs: a survey
• Improved Edge-Coloring with Three Colors
• 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
• Parameterized and Exact Algorithms for Class Domination Coloring
• Linear Index Coding via Semidefinite Programming
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• Matrix Relaxations in Combinatorial Optimization
• Title not available (Why is that?)
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Coloring -colorable graphs using relatively small palettes
• Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
• Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
• Title not available (Why is that?)

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)