Bounding the Independence Number of a Graph

DOI10.1016/S0304-0208(08)72453-8MaRDI QIDQ3967569zbMATH OpenOpenAlexWikidataFDO

Authors 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

NP-completeindependence number

Mathematics Subject Classification ID

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

Cited in

(5)

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

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

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