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