On the tractability of coloring semirandom graphs

DOI10.1016/j.ipl.2008.04.011zbMath1191.68461OpenAlexW2022986417MaRDI QIDQ975431

Dan Vilenchik, Julia Böttcher

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.04.011

zbMATH Keywords

graph algorithmsaverage case analysis\(k\)-coloringsemi-random models

Mathematics Subject Classification ID

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

Related Items (1)

A NEW APPROACH TO THE VERTEX COLORING PROBLEM

Cites Work

• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Zero knowledge and the chromatic number
• Geometric algorithms and combinatorial optimization.
• Heuristics for semirandom graph problems
• New approximation guarantee for chromatic number
• Conditional hardness for approximate coloring
• Approximate graph coloring by semidefinite programming
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Coloring Random and Semi-Random k-Colorable Graphs
• Semirandom Models as Benchmarks for Coloring Algorithms
• Colouring Semirandom Graphs
• The chromatic number of random graphs
• The chromatic number of random graphs

This page was built for publication: On the tractability of coloring semirandom graphs