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

4-colorable graphApproximation algorithmscoloringGraph coloringSemidefinite programming

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

(20)

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

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)