Bounding the Independence Number of a Graph

DOI10.1016/S0304-0208(08)72453-8zbMath0502.05051OpenAlexW1016912189WikidataQ89220149 ScholiaQ89220149MaRDI QIDQ3967569

László Lovász

Publication date: 1982

Published in: North-Holland Mathematics Studies (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-0208(08)72453-8

zbMATH Keywords

independence numberNP-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (5)

A Derivation of Lovász' Theta via Augmented Lagrange Duality ⋮ A note on graph colorings and graph polynomials ⋮ On two generalizations of the Alon-Tarsi polynomial method ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Computing the chromatic number using graph decompositions via matrix rank

This page was built for publication: Bounding the Independence Number of a Graph