Independence numbers of graphs and generators of ideals |
| |
Authors: | Shuo-Yen Robert Li Wen-Ch’ing Winnie Li |
| |
Institution: | (1) Department of Mathematics, University of Illinois at Chicago Circle, 60680 Chicago, Illinois, USA;(2) Present address: Department of Mathematics, Pennsylvania State University, 16802 University Park, PA |
| |
Abstract: | 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 oft-designs. The main theorem suggests a new approach to the Clique Problem which isNP-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.
Research supported in part by NSF Grant MCS77-03533. |
| |
Keywords: | 05 C 35 13 A 15 05 C 15 |
本文献已被 SpringerLink 等数据库收录! |
|