An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
type: Item
instance of: scholarly article
title: An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
zbMATH Open document ID: 1184.05041
author: Amin Coja-Oghlan
author: Lars Kuhtz
published in: Information Processing Letters
publication date: 2010-01-29T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5664492
zbMATH Keywords: approximation algorithms
zbMATH Keywords: graph algorithms
MaRDI profile type: Publication
full work available at URL: j.ipl.2006.05.004
OpenAlex ID: W2007944679
cites work: The chromatic number of random graphs
cites work: Paths in graphs
cites work: The Lovász Number of Random Graphs
cites work: MAX k‐CUT and approximating the chromatic number of random graphs
cites work: Exact and approximative algorithms for coloring G(n,p)
cites work: Zero knowledge and the chromatic number
cites work: Q3122905
cites work: On colouring random graphs
cites work: Approximate graph coloring by semidefinite programming
cites work: Q4428908
cites work: Approximating the independence number and the chromatic number in expected polynomial time
cites work: The greedy coloring is a bad probabilistic algorithm
cites work: A note on the complexity of the chromatic number problem
DOI: 10.1016/J.IPL.2006.05.004
description: scientific article; zbMATH DE number 5664492