# On 𝓕-independence in graphs

Frank Göring; Jochen Harant; Dieter Rautenbach; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 2, page 377-383
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topFrank Göring, et al. "On 𝓕-independence in graphs." Discussiones Mathematicae Graph Theory 29.2 (2009): 377-383. <http://eudml.org/doc/270163>.

@article{FrankGöring2009,

abstract = {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.},

author = {Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {independence; complexity; probabilistic method},

language = {eng},

number = {2},

pages = {377-383},

title = {On 𝓕-independence in graphs},

url = {http://eudml.org/doc/270163},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Frank Göring

AU - Jochen Harant

AU - Dieter Rautenbach

AU - Ingo Schiermeyer

TI - On 𝓕-independence in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 2

SP - 377

EP - 383

AB - 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.

LA - eng

KW - independence; complexity; probabilistic method

UR - http://eudml.org/doc/270163

ER -

## References

top- [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. Zbl1075.05066
- [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. Zbl0902.05026
- [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. Zbl0904.05045
- [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. Zbl0623.05031
- [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. Zbl0223.05101
- [8] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & Hall, 2005). Zbl1057.05001
- [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. Zbl0959.05080
- [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. Zbl1028.01503
- [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).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.