ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


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


Frank Göring

Fakultät für Mathematik
TU Chemnitz, 09107 Chemnitz, Germany

Jochen Harant, Dieter Rautenbach

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

Ingo Schiermeyer

Institut für Diskrete Mathematik und Algebra
TU Bergakademie Freiberg, 09596 Freiberg, Germany


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.


[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