Coloring -colorable graphs using relatively small palettes

DOI10.1016/S0196-6774(02)00217-1MaRDI QIDQ4806594zbMATH OpenOpenAlexFDO

Authors Eran Halperin, Ram Nathaniel, Uri Zwick

Publication date 14 May 2003

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0196-6774(02)00217-1

zbMATH Keywords

coloringApproximation algorithmsSemidefinite programmingGraph coloring4-colorable graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Coloring \(k\)-colorable graphs using smaller palettes
• New approximation algorithms for graph coloring
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Coloring 3-colorable graphs with \(o(n^{1/5})\) colors

Cited in

(19)

• Coloring graphs having few colorings over path decompositions
• Approximating the orthogonality dimension of graphs and hypergraphs
• scientific article; zbMATH DE number 7561683 (Why is no real title available?)
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Coloring \(k\)-colorable graphs using smaller palettes
• Computing the partition function for graph homomorphisms
• Linear index coding via semidefinite programming
• Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
• Copositive programming motivated bounds on the stability and the chromatic numbers
• Wireless capacity with arbitrary gain matrix
• scientific article; zbMATH DE number 764415 (Why is no real title available?)
• Almost all k-colorable graphs are easy to color
• Convex relaxations and integrality gaps
• Hardness of rainbow coloring hypergraphs
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
• Linear index coding via semidefinite programming

This page was built for publication: Coloring -colorable graphs using relatively small palettes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4806594)