Approximating the independence number and the chromatic number in expected polynomial time

DOI10.1023/A:1013899527204zbMath0995.05055OpenAlexW1492831324MaRDI QIDQ1598877

Van H. Vu, Michael Krivelevich

Publication date: 28 May 2002

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1013899527204

zbMATH Keywords

independence numberchromatic numberapproximating algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (12)

Concentration of norms and eigenvalues of random matrices ⋮ An improved algorithm for approximating the chromatic number of \(G_{n,p}\) ⋮ Optimal detection of sparse principal components in high dimension ⋮ Approximating independent set in perturbed graphs ⋮ Concentration for noncommutative polynomials in random matrices ⋮ On-line list colouring of random graphs ⋮ Spectral norm of random matrices ⋮ Wigner random matrices with non-symmetrically distributed entries ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Approximating Independent Set and Coloring in Random Uniform Hypergraphs ⋮ Eigenvectors of random graphs: Nodal Domains ⋮ The resolution complexity of random graph \(k\)-colorability

This page was built for publication: Approximating the independence number and the chromatic number in expected polynomial time