Article ID Journal Published Year Pages File Type
4648888 Discrete Mathematics 2010 11 Pages PDF
Abstract

Let HH be a set of graphs. A graph is called HH-free   if it does not contain a copy of a member of HH as an induced subgraph. If HH is a graph then GG is called HH-free   if it is {H}{H}-free. Plummer, Stiebitz, and Toft proved that, for every K3¯-free graph HH on at most four vertices, every {K3¯,H}-free graph GG has a collection of ⌈|V(G)|/2⌉⌈|V(G)|/2⌉ many pairwise adjacent vertices and edges (where a vertex  vvand an edge  eeare adjacent   if vv is disjoint from the set V(e)V(e) of endvertices of ee and adjacent to some vertex of V(e)V(e), and two edges  eeand  ffare adjacent   if V(e)V(e) and V(f)V(f) are disjoint and some vertex of V(e)V(e) is adjacent to some vertex of V(f)V(f)). Here we generalize this statement to K3¯-free graphs HH on at most five vertices.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,