History
Year:
-
Type:
Journal
Book
Article
Please fill in your query. A complete syntax description you will find on the General Help page.
Independence, odd girth, and average degree. (English)
J. Graph Theory 67, No. 2, 96-111 (2011).
Summary: We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle-free graphs of maximum degree at most three due to {\it C. C. Heckman} and {\it R. Thomas} [Discrete Math. 233, No.1-3, 233-237 (2001; Zbl 0982.05071)] to arbitrary triangle-free graphs. For connected triangle-free graphs of order $n$ and size $m$, our result implies the existence of an independent set of order at least $(4n - m - 1)/7$.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!