New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs
journal contributionposted on 2013-12-03, 00:00 authored by Kunal Dutta, Dhruv Mubayi, C. R. Subramanian
We obtain new lower bounds for the independence number of K-r-free graphs and linear k-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99-107]. Our proof technique is an extension of a method of Caro [New Results on the Independence Number, Technical report, Tel Aviv University, 1979] and Wei [A Lower Bound on the Stability Number of a Simple Graph, TM 81-11217-9, Bell Laboratories, Berkley Heights, NJ, 1981], and we also give a new short proof of the main result of Caro and Tuza using this approach. As byproducts, we also obtain some nontrivial identities involving binomial coefficients, which may be of independent interest.
NSF grant DMS 0969092.
Publisher StatementThe original version is available through Society for Industrial and Applied Mathematics at DOI: 10.1137/110839023.
PublisherSociety for Industrial and Applied Mathematics