کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648888 | 1342434 | 2010 | 11 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 310, Issue 20, 28 October 2010, Pages 2714–2724