×

Remarks on component factors in \(K_{1,r}\)-free graphs. (English) Zbl 1514.05128

Summary: An \(\mathcal{F}\)-factor is a spanning subgraph \(H\) such that each connected component of \(H\) is isomorphic to some graph in \(\mathcal{F}\). We use \(P_k\) and \(K_{1,r}\) to denote the path of order \(k\) and the star of order \(r + 1\), respectively. In particular, \(H\) is called a \(\{ P_2, P_3\}\)-factor of \(G\) if \(\mathcal{F} = \{P_2, P_3\}; H\) is called a \(P_{\geq k}\)-factor of \(G\) if \(\mathcal{F} = \{P_k, P_{k+1},\ldots\}\), where \(k \geq 2; H\) is called an \(\mathcal{S}_n\)-factor of \(G\) if \(\mathcal{F} = \{P_2, P_3, K_{1,3},\ldots, K_{1,n}\}\), where \(n \geq 2\). A graph \(G\) is called a \(\mathcal{P}_{\geq k}\)-factor covered graph if there is a \(\mathcal{P}_{\geq k}\)-factor of \(G\) including \(e\) for any \(e \in E(G)\). We call a graph \(G\) is \(K_{1,r}\)-free if \(G\) does not contain an induced subgraph isomorphic to \(K_{1,r}\). In this paper, we give a minimum degree condition for the \(K_{1,r}\)-free graph with an \(\mathcal{S}_n\)-factor and the \(K_{1,r}\)-free graph with a \(\mathcal{P}_{\geq 3}\)-factor, respectively. Further, we obtain sufficient conditions for \(K_{1,r}\)-free graphs to be \(\mathcal{P}_{\geq 2}\)-factor, \(\mathcal{P}_{\geq 3}\)-factor or \(\{P_2, P_3\}\)-factor covered graphs. In addition, examples show that our results are sharp.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C38 Paths and cycles