Geodesic
On Selkow’s Bound on the Independence Number of Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 655-657.

Voir la notice de l'article provenant de la source Library of Science

For a graph G with vertex set V (G) and independence number α (G), Selkow [A Probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363–365] established the famous lower bound ∑_ v ∈ V (G) 1d(v)+1 ( 1+ max{ d(v) d(v)+1 - ∑_ u ∈ N(v) 1 d(u)+1 ,0 } ) on α (G), where N(v) and d(v) = | N(v) | denote the neighborhood and the degree of a vertex v ∈ V (G), respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.
Keywords: graph, independence number 
@article{DMGT_2019_39_3_a3,
     author = {Harant, Jochen and Mohr, Samuel},
     title = {On {Selkow{\textquoteright}s} {Bound} on the {Independence} {Number} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {655--657},
     publisher = {mathdoc},
     volume = {39},
     number = {3},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a3/}
}
TY  - JOUR
AU  - Harant, Jochen
AU  - Mohr, Samuel
TI  - On Selkow’s Bound on the Independence Number of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 655
EP  - 657
VL  - 39
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a3/
LA  - en
ID  - DMGT_2019_39_3_a3
ER  - 
%0 Journal Article
%A Harant, Jochen
%A Mohr, Samuel
%T On Selkow’s Bound on the Independence Number of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 655-657
%V 39
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a3/
%G en
%F DMGT_2019_39_3_a3
Harant, Jochen; Mohr, Samuel. On Selkow’s Bound on the Independence Number of Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 655-657. http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a3/

[1] N. Alon and J.H. Spencer, The Probabilistic Method (Wiley, New York, 1992).

[2] Y. Caro, New Results on the Independence Number (Technical Report, Tel-Aviv University, 1979).

[3] S.M. Selkow, A Probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363–365. doi:10.1016/0012-365X(93)00102-B

[4] V.K. Wei, A Lower Bound on the Stability Number of a Simple Graph (Technical Memorandum, TM 81 - 11217 - 9, Bell laboratories, 1981).