Coloring -colorable graphs using relatively small palettes

DOI10.1016/S0196-6774(02)00217-1zbMATH Open1030.68067OpenAlexW2074891431MaRDI QIDQ4806594FDOQ4806594

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

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

zbMATH Keywords

coloringApproximation algorithmsSemidefinite programmingGraph coloring4-colorable graph

Mathematics Subject Classification ID

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

Cited In (19)

• Coloring graphs having few colorings over path decompositions
• Title not available (Why is that?)
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
• Coloring \(k\)-colorable graphs using smaller palettes
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)