DMGT

Discussiones Mathematicae Graph Theory 29(2) (2009) 377-383
DOI: https://doi.org/10.7151/dmgt.1453

ON F-INDEPENDENCE IN GRAPHS

Frank Göring

Fakultät für Mathematik
TU Chemnitz, 09107 Chemnitz, Germany
e-mail: frank.goering@mathematik.tu-chemnitz.de

Jochen Harant, Dieter Rautenbach

Institut für Mathematik
TU Ilmenau, Postfach 100565, 98684 Ilmenau, Germany

e-mail:	jochen.harant@tu-ilmenau.de
e-mail:	dieter.rautenbach@tu-ilmenau.de

Ingo Schiermeyer

Institut für Diskrete Mathematik und Algebra
TU Bergakademie Freiberg, 09596 Freiberg, Germany
e-mail: schierme@math.tu-freiberg.de

Abstract

Let F be a set of graphs and for a graph G let α_F(G) and α _F^*(G) denote the maximum order of an induced subgraph of G which does not contain a graph in F as a subgraph and which does not contain a graph in F as an induced subgraph, respectively. Lower bounds on α_F(G) and α_F^*(G) are presented.

Keywords: independence, complexity, probabilistic method.

2000 Mathematics Subject Classification: 05C69.

References

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

Received 25 March 2008
Revised 26 March 2008
Accepted 23 May 2008