A lower bound on the independence number of a graph in terms of degrees

Jochen Harant; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 3, page 431-437
  • ISSN: 2083-5892

Abstract

top
For a connected and non-complete graph, a new lower bound on its independence number is proved. It is shown that this bound is realizable by the well known efficient algorithm MIN.

How to cite

top

Jochen Harant, and Ingo Schiermeyer. "A lower bound on the independence number of a graph in terms of degrees." Discussiones Mathematicae Graph Theory 26.3 (2006): 431-437. <http://eudml.org/doc/270505>.

@article{JochenHarant2006,
abstract = {For a connected and non-complete graph, a new lower bound on its independence number is proved. It is shown that this bound is realizable by the well known efficient algorithm MIN.},
author = {Jochen Harant, Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {independence; stability; algorithm; greedy algorithm},
language = {eng},
number = {3},
pages = {431-437},
title = {A lower bound on the independence number of a graph in terms of degrees},
url = {http://eudml.org/doc/270505},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Jochen Harant
AU - Ingo Schiermeyer
TI - A lower bound on the independence number of a graph in terms of degrees
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 3
SP - 431
EP - 437
AB - For a connected and non-complete graph, a new lower bound on its independence number is proved. It is shown that this bound is realizable by the well known efficient algorithm MIN.
LA - eng
KW - independence; stability; algorithm; greedy algorithm
UR - http://eudml.org/doc/270505
ER -

References

top
  1. [1] E. Bertram and P. Horak, Lower bounds on the independence number, Geombinatorics V (1996) 93-98. Zbl0972.05024
  2. [2] Y. Caro, New results on the independence number (Technical Report. Tel-Aviv University, 1979). 
  3. [3] Y. Caro and Z. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107, doi: 10.1002/jgt.3190150110. Zbl0753.68079
  4. [4] S. Fajtlowicz, On the size of independent sets in graphs, Proc. 9th S-E Conf. on Combinatorics, Graph Theory and Computing, Boca Raton 1978, 269-274. Zbl0434.05044
  5. [5] S. Fajtlowicz, Independence, clique size and maximum degree, Combinatorica 4 (1984) 35-38, doi: 10.1007/BF02579154. Zbl0576.05025
  6. [6] J. Harant, A lower bound on the independence number of a graph, Discrete Math. 188 (1998) 239-243, doi: 10.1016/S0012-365X(98)00048-X. Zbl0958.05067
  7. [7] J. Harant and I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math. 232 (2001) 131-138, doi: 10.1016/S0012-365X(00)00298-3. 
  8. [8] O. Murphy, Lower bounds on the stability number of graphs computed in terms of degrees, Discrete Math. 90 (1991) 207-211, doi: 10.1016/0012-365X(91)90357-8. Zbl0755.05055
  9. [9] 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. Zbl0810.05039
  10. [10] J.B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983) 83-87, doi: 10.1016/0012-365X(83)90273-X. Zbl0516.05053
  11. [11] J.B. Shearer, A note on the independence number of triangle-free graphs, II, J. Combin. Theory (B) 53 (1991) 300-307, doi: 10.1016/0095-8956(91)90080-4. Zbl0753.05074
  12. [12] V.K. Wei, A lower bound on the stability number of a simple graph (Bell Laboratories Technical Memorandum 81-11217-9, Murray Hill, NJ, 1981). 

NotesEmbed ?

top

You must be logged in to post comments.