Wissen, was gut ist. Studieren in Chemnitz.
Göring, Frank; Harant, Jochen; Rautenbach, Dieter; Schiermeyer, Ingo : On F-Independence in Graphs

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