Forbidden induced subgraphs for star-free graphs
Forbidden induced subgraphs for star-free graphs
复制标题
DOI：
10.1016/j.disc.2011.07.022
复制
发表时间：
2011-11
期刊：
影响因子：
--
通讯作者：
J. Fujisawa;K. Ota;K. Ozeki;Gabriel Sueiro
中科院分区：
文献类型：
--
作者：
J. Fujisawa;K. Ota;K. Ozeki;Gabriel Sueiro
设H是连通图族。一个图G称为H-自由的，如果对H中的每个图H，G都是H-自由的.在Aldred et al.（2010）[1]中指出，存在一类不含爪的导出子图的连通图H，其性质是含爪的无H-free连通图的集合是有限的，只要这些图的最小度至少为2，最大度至少为3。在同一工作中，还询问是否有其他家庭拥有同样的财产。在本文中，我们通过解决更广泛的问题来回答这个问题。我们不仅考虑了无爪图，而且考虑了更一般的无星图。具体地说，当t≥3时，我们刻画了所有的图族H，使得每一个足够大的H-free连通图都是K1，t-free的。此外，对于t=3的情况，我们给出了当对每个正整数k加上条件<$H <$≤k时得到的族。
Let H be a family of connected graphs. A graph G is said to be H-free if G is H-free for every graph H in H. In Aldred et al. (2010) [1], it was pointed that there is a family of connected graphs H not containing any induced subgraph of the claw having the property that the set of H-free connected graphs containing a claw is finite, provided also that those graphs have minimum degree at least 2 and maximum degree at least 3. In the same work, it was also asked whether there are other families with the same property. In this paper, we answer this question by solving a wider problem. We consider not only claw-free graphs but the more general class of star-free graphs. Concretely, given t≥3, we characterize all the graph families H such that every large enough H-free connected graph is K1,t-free. Additionally, for the case t=3, we show the families that one gets when adding the condition ∣H∣≤k for each positive integer k.