Independence, induced subgraphs, and domination in $K_{1,r}$-free graphs

Abstract

Let $G$ be a graph and $\mathcal{F}$ a family of graphs. Define $\hat{I}{\pm }_{\mathcal{F}}(G)$ as the maximum order of any induced subgraph of $G$ that belongs to the family $\mathcal{F}$. For the family $\mathcal{F}$ of graphs with \emph{chromatic number} at most~$k$, we prove that if $G$ is $K_{1,r}$-free, then $\hat{I}{\pm }_{\mathcal{F}}(G)\le (r-1)k{\hat{I}}^3(G)$, where ${\hat{I}}^3(G)$ is the \emph{domination number}. When $\mathcal{F}$ is the family of empty graphs, this bound simplifies to $\hat{I}\pm (G)\le 2{\hat{I}}^3(G)$ for $K_{1,3}$-free (claw-free) graphs, where $\hat{I}\pm (G)$ is the \emph{independence number} of $G$. For $d$-regular graphs, this is further refined to the bound $\hat{I}\pm (G)\le 2\left(\frac{d+1}{d+2}\right){\hat{I}}^3(G)$, which is tight for $d\in \{2,3,4\}$. Using Ramsey theory, we extend this framework to edge-hereditary graph families, showing that for $K_{1,r}$-free graphs, we have $\hat{I}{\pm }_{\mathcal{F}}(G)\le r(K_r,{\mathcal{F}}^{\ast }){\hat{I}}^3(G)$, where ${\mathcal{F}}^{\ast }$ is the set of graphs not in $\mathcal{F}$. Specializing to $K_q$-free graphs, we show $\hat{I}{\pm }_{\mathcal{F}}(G)\le (r(K_q,K_r)-1){\hat{I}}^3(G)$. Finally, for the \emph{$k$-independence number} $\hat{I}{\pm }_k(G)$, we prove that if $G$ is $K_{1,r}$-free with order $n$ and minimum degree $\hat{I}´\ge k+1$, \[ α_k(G) \le \left( \frac{(r-1)(k+1)}{δ- k + (r-1)(k+1)} \right) n, \] and this bound is sharp for all parameters.