Journal of Combinatorics

Volume 9 (2018)

Number 4

Forbidden subgraphs for $k$ vertex-disjoint stars

Pages: 721 – 738

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

Authors

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)

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

Received 8 June 2014

Published 7 December 2018