Randomized graph products, chromatic numbers, and Lovasz j-function

DOI10.1145/225058.225281zbMath1058.94517OpenAlexW2005412366MaRDI QIDQ4234113

No author found.

Publication date: 1995

Published in: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing - STOC '95 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/225058.225281

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15)

Related Items (11)

New lower bounds for the Shannon capacity of odd cycles ⋮ Algorithmic and explicit determination of the Lovász number for certain circulant graphs ⋮ Semidefinite programming in combinatorial optimization ⋮ Derandomized parallel repetition theorems for free games ⋮ Approximating the independence number via the \(\vartheta\)-function ⋮ Orthonormal representations of \(H\)-free graphs ⋮ Lovász, Vectors, Graphs and Codes ⋮ The complexity of properly learning simple concept classes ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Zero knowledge and the chromatic number ⋮ Clique, chromatic, and Lovász numbers of certain circulant graphs

This page was built for publication: Randomized graph products, chromatic numbers, and Lovasz j-function