Göring, Frank ; Harant, Jochen ; Rautenbach, Dieter ; Schiermeyer, Ingo : On F-Independence in Graphs
- Author(s):
-
Göring, Frank
Harant, Jochen
Rautenbach, Dieter
Schiermeyer, Ingo
- Title:
- On F-Independence in Graphs
- Electronic source:
-
application/pdf
- Preprint series:
- Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 18, 2007
- Mathematics Subject Classification:
-
05C69 [ Dominating sets, independent sets, cliques ] - Abstract:
- Abstract. Let F be a set of graphs and for a graph G let alpha_F(G) and alpha_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 alpha_F(G) and alpha_F*(G) are presented.
- Keywords:
- independence, graph, complexity, probabilistic method
- Language:
-
English
- Publication time:
- 10 / 2007
