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

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)