Journal of Combinatorics

Volume 9 (2018)

Number 4

Forbidden subgraphs for $k$ vertex-disjoint stars

Pages: 721 – 738



Michitaka Furuya (College of Liberal Arts and Science, Kitasato University, Sagamihara, Kanagawa, Japan)

Naoki Matsumoto (Department of Computer and Information Science, Seikei University, Musashino-shi, Tokyo, Japan)


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$.


vertex-disjoint star, forbidden subgraph, starfree graph

2010 Mathematics Subject Classification


This work was supported by JSPS KAKENHI Grant number 26800086.

Received 8 June 2014

Published 7 December 2018