Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 4

### Forbidden subgraphs for $k$ vertex-disjoint stars

Pages: 721 – 738

DOI: http://dx.doi.org/10.4310/JOC.2018.v9.n4.a8

#### Authors

#### Abstract

For a connected graph $H$, a graph $G$ is said to be $H$-*free* if $G$ does not contain $H$ as an induced subgraph. In this context, $H$ is called a *forbidden subgraph*. In this paper, we study a transition of forbidden subgraphs for the existence of vertex-disjoint stars. For $t \geq 1, k \geq 1$ and $d \geq t$, let $\mathcal{H}(t, k, d)$ be the family of connected graphs $H$ such that every $H$-free graph $G$ of sufficiently large order with $\sigma (G) \geq d$ has $k$ vertex-disjoint $K_{1,t}$. We characterize the family $\mathcal{H}(t, k, d)$ for almost all triples $(t, k, d)$. In particular, we give a complete characterization of $\mathcal{H}(t, k, d)$ for $t \leq 4$.

#### Keywords

vertex-disjoint star, forbidden subgraph, starfree graph

#### 2010 Mathematics Subject Classification

05C70

This work was supported by JSPS KAKENHI Grant number 26800086.

Received 8 June 2014