Independence numbers of graphs and generators of ideals

Shuo Yen Robert Li, Wen Ch ing Winnie Li

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


This article investigates the generators of certain homogeneous ideals which are associated with graphs with bounded independence numbers. These ideals first appeared in the theory of t-designs. The main theorem suggests a new approach to the Clique Problem which is NP-complete. This theorem has a more general form in commutative algebra dealing with ideals associated with unions of linear varieties. This general theorem is stated in the article; a corollary to it generalizes Turán's theorem on the maximum graphs with a prescribed clique number.

Original languageEnglish (US)
Pages (from-to)55-61
Number of pages7
Issue number1
StatePublished - Mar 1981

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'Independence numbers of graphs and generators of ideals'. Together they form a unique fingerprint.

Cite this