Geodesic
On -independence in graphs
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 2, pp. 377-383.

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

Let be a set of graphs and for a graph G let α_(G) and α*_(G) denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on α_(G) and α*_(G) are presented.
Keywords: independence, complexity, probabilistic method 
@article{DMGT_2009_29_2_a11,
     author = {G\"oring, Frank and Harant, Jochen and Rautenbach, Dieter and Schiermeyer, Ingo},
     title = {On -independence in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {377--383},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a11/}
}
TY  - JOUR
AU  - Göring, Frank
AU  - Harant, Jochen
AU  - Rautenbach, Dieter
AU  - Schiermeyer, Ingo
TI  - On -independence in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 377
EP  - 383
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a11/
LA  - en
ID  - DMGT_2009_29_2_a11
ER  - 
%0 Journal Article
%A Göring, Frank
%A Harant, Jochen
%A Rautenbach, Dieter
%A Schiermeyer, Ingo
%T On -independence in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 377-383
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a11/
%G en
%F DMGT_2009_29_2_a11
Göring, Frank; Harant, Jochen; Rautenbach, Dieter; Schiermeyer, Ingo. On -independence in graphs. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 2, pp. 377-383. http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a11/

[1] N. Alon and J.H. Spencer, The probablilistic method (2nd ed.), (Wiley, 2000), doi: 10.1002/0471722154.

[2] R. Boliac, C. Cameron and V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin. 72 (2004) 241-253.

[3] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.

[4] M. Borowiecki, D. Michalak and E. Sidorowicz, Generalized domination, independence and irredudance in graphs, Discuss. Math. Graph Theory 17 (1997) 147-153, doi: 10.7151/dmgt.1048.

[5] Y. Caro, New results on the independence number, Technical Report (Tel-Aviv University, 1979).

[6] Y. Caro and Y. Roditty, On the vertex-independence number and star decomposition of graphs, Ars Combin. 20 (1985) 167-180.

[7] G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbiden subgraphs, J. Combin. Theory 10 (1971) 12-41, doi: 10.1016/0095-8956(71)90065-7.

[8] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman Hall, 2005).

[9] M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman and Company, San Francisco, 1979).

[10] J. Harant, A. Pruchnewski and M. Voigt, On Dominating Sets and Independendent Sets of Graphs, Combinatorics, Probability and Computing 8 (1999) 547-553, doi: 10.1017/S0963548399004034.

[11] S. Hedetniemi, On hereditary properties of graphs, J. Combin. Theory (B) 14 (1973) 349-354, doi: 10.1016/S0095-8956(73)80009-7.

[12] V. Vadim and D. de Werra, Special issue on stability in graphs and related topics, Discrete Appl. Math. 132 (2003) 1-2, doi: 10.1016/S0166-218X(03)00385-8.

[13] Zs. Tuza, Lecture at Conference of Hereditarnia (Zakopane, Poland, September 2006).

[14] 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).