110839023.pdf (212.1 kB)
Download file

New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs

Download (212.1 kB)
journal contribution
posted on 03.12.2013, 00:00 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.

Funding

NSF grant DMS 0969092.

History

Publisher Statement

The original version is available through Society for Industrial and Applied Mathematics at DOI: 10.1137/110839023.

Publisher

Society for Industrial and Applied Mathematics

Language

en_US

issn

0895-4801

Issue date

01/01/2012

Usage metrics

Categories

Keywords

Exports