On proving that a graph has no large clique: A connection with Ramsey theory

DOI10.1016/0020-0190(95)00209-XzbMath1004.68535OpenAlexW1978708669MaRDI QIDQ1351164

Richard J. Lipton

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00209-x

zbMATH Keywords

computational complexityRamsey theoryclique approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Non-deterministic exponential time has two-prover interactive protocols
• The Complexity of Near-Optimal Graph Coloring
• On the hardness of approximating minimization problems
• Efficient probabilistically checkable proofs and applications to approximations
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On proving that a graph has no large clique: A connection with Ramsey theory