Exact and approximative algorithms for coloring G(n,p)

DOI10.1002/rsa.20007zbMath1042.05035OpenAlexW3082999210MaRDI QIDQ4736774

Amin Coja-Oghlan, Anusch Taraz

Publication date: 6 August 2004

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20007

zbMATH Keywords

approximation algorithmrandom graphschromatic numbercoloring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

An improved algorithm for approximating the chromatic number of \(G_{n,p}\) ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ On-line list colouring of random graphs ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ A note on coloring sparse random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization
• Fundamentals of Computation Theory
• Almost all graphs with average degree 4 are 3-colorable

This page was built for publication: Exact and approximative algorithms for coloring G(n,p)