TY - JOUR
T1 - Forbidden induced subgraphs for star-free graphs
AU - Fujisawa, Jun
AU - Ota, Katsuhiro
AU - Ozeki, Kenta
AU - Sueiro, Gabriel
N1 - Funding Information:
We would like to thank the referees for their helpful comments and suggestions. The work of the first author was supported by JSPS Grant-in-Aid for Young Scientists (Start-up).
PY - 2011/11/6
Y1 - 2011/11/6
N2 - 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.
AB - 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.
KW - Claw-free
KW - Forbidden subgraph
KW - Star-free
UR - http://www.scopus.com/inward/record.url?scp=81155161915&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=81155161915&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2011.07.022
DO - 10.1016/j.disc.2011.07.022
M3 - Article
AN - SCOPUS:81155161915
SN - 0012-365X
VL - 311
SP - 2475
EP - 2484
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 21
ER -