Lower bounds on the independence number in terms of the degrees

Jerrold R. Griggs

Type: Article

Publication Date: 1983-02-01

Citations: 86

DOI: https://doi.org/10.1016/0095-8956(83)90003-5

View Publication

Locations

Journal of Combinatorial Theory Series B - View

Similar Works

Action	Title	Year	Authors
+	The lower bound on independence number	2002	Yusheng Li Cecil Rousseau Wenan Zang
+	The independence number of graphs in terms of degrees	1993	Stanley M. Selkow
+	Bounds for the independence number of a graph	2011	William Willis
+	A new lower bound on the independence number of graphs	2013	Éric Angel Romain Campigotto Christian Laforest
+	Upper bounds on the independence and the clique covering number	2003	C. Van Nuffelen K. Van Rompay
+	A lower bound on the independence number of a graph	1998	Jochen Harant
+ PDF Chat	Tighter bounds on the independence number of the Birkhoff graph	2022	Leonardo N. Coregliano Fernando Granha Jeronimo
+	Sharp upper bounds on the $k$-independence number in regular graphs	2019	Zhenyu Taoqiu O Suil Yongtang Shi
+	A lower bound on independence in terms of degrees	2011	Jochen Harant
+	Estimates of the number of independent sets in graphs with a fixed independence number	2009	A. B. Dainyak
+	On the Number of Independence of a Class of Graphs	2000	Evgeni Nedialkov N. Nenov
+	Lower bounds for the independence numbers of some distance graphs with vertices in {−1, 0, 1} n	2009	V. K. Lyubimov А. М. Райгородский
+	Upper bound for the number of independent sets in graphs	2007	А. А. Сапоженко
+	On estimates of degrees of linear independence for some numbers	1994	П. Л. Иванков
+	Lower bounds for independence numbers of some locally sparse graphs	2012	Yusheng Li Qizhong Lin
+	Approximating the minimum maximal independence number	1993	Magnús M. Halldórsson
+	Minimum degree, independence number and regular factors	1995	T. Nießen
+	Independence, clique size and maximum degree	1984	Siemion Fajtlowicz
+	Estimates of the independence number of a hypergraph and the Ryser conjecture	1997	V. E. Tarakanov
+	On the coefficients of the independence polynomial of graphs	2016	Shuchao Li Lin Liu Yueyu Wu

Works That Cite This (57)

Action	Title	Year	Authors
+ PDF Chat	Approximating the Caro-Wei Bound for Independent Sets in Graph Streams	2018	Graham Cormode Jacques Dark Christian Konrad
+ PDF Chat	Large induced degenerate subgraphs	1987	Noga Alon J. Kahn Paul Seymour
+	MAX for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" id="d1e1482" altimg="si19.gif"><mml:mi>k</mml:mi></mml:math>-independence in multigraphs	2019	Nevena Francetić Sara Herke Daniel Horsley
+	A sharp lower bound on the independence number of k-regular connected hypergraphs with rank R	2024	Zhongzheng Tang Haoyang Zou Zhuo Diao
+	New bounds for contagious sets	2012	Daniel Reichman
+	An upper bound on the Ramsey numbers R(3, k)	1983	Jerrold R. Griggs
+	Edge density and independence ratio in triangle-free graphs with maximum degree three	1996	Jerrold R. Griggs Owen Murphy
+	Bounding the feedback vertex number of digraphs in terms of vertex degrees	2011	Hermann Gruber
+	A note on greedy algorithms for the maximum weighted independent set problem	2002	Shuichi Sakai Mitsunori Togasaki Koichi Yamazaki
+	New potential functions for greedy independence and coloring	2014	Piotr Borowiecki Dieter Rautenbach

Works Cited by This (6)

Action	Title	Year	Authors
+	Extremal Graph Theory	1978	Béla Bollobás
+	An upper bound on the Ramsey numbers R(3, k)	1983	Jerrold R. Griggs
+	On the independence ratio of a graph	1978	Michael O. Albertson Joan P. Hutchinson
+	A note on Ramsey numbers	1980	Miklós Ajtai János Komlós Endre Szemerédi
+	Some applications of graph theory to finite groups	1983	Edward A. Bertram
+ PDF Chat	Some Ramsey-type numbers and the independence ratio	1979	William Staton