An improved algorithm for approximating the chromatic number of G_n,p

DOI10.1016/J.IPL.2006.05.004MaRDI QIDQ845732zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Lars Kuhtz

Publication date 29 January 2010

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

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

zbMATH Keywords

approximation algorithmsgraph algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1962838
• Approximating the independence number and the chromatic number in expected polynomial time
• Approximating the chromatic polynomial
• Exact and approximative algorithms for coloring G(n,p)
• scientific article; zbMATH DE number 2038711

Cites work

• A note on the complexity of the chromatic number problem
• Approximate graph coloring by semidefinite programming
• Approximating the independence number and the chromatic number in expected polynomial time
• Exact and approximative algorithms for coloring G(n,p)
• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• scientific article; zbMATH DE number 1984543 (Why is no real title available?)
• MAX k‐CUT and approximating the chromatic number of random graphs
• On colouring random graphs
• Paths in graphs
• The chromatic number of random graphs
• The chromatic number of random graphs
• The greedy coloring is a bad probabilistic algorithm
• The Lovász Number of Random Graphs
• Zero knowledge and the chromatic number

Cited in

(12)

• A randomised heuristical algorithm for estimating the chromatic number of a graph
• Approximating the independence number and the chromatic number in expected polynomial time
• Fractionally total colouring \(G_{n,p}\)
• scientific article; zbMATH DE number 1670810 (Why is no real title available?)
• Approximating the chromatic polynomial
• An approximate algorithm for the chromatic number of graphs
• An approximation chromatic number of a graph
• scientific article; zbMATH DE number 4213473 (Why is no real title available?)
• scientific article; zbMATH DE number 2038711 (Why is no real title available?)
• Exact and approximative algorithms for coloring G(n,p)
• Report 7/2006: Algorithmic Graph Theory (February 12th -- February 18th, 2006)
• \([r,s,t]\)-coloring of trees and bipartite graphs

This page was built for publication: An improved algorithm for approximating the chromatic number of \(G_{n,p}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845732)