Sufficient conditions for the existence of a path-factor which are related to odd components

Abstract

In this paper, we are concerned with sufficient conditions for the existence of a $\{P_2,P_{2k+1}\}$-factor. We prove that for $k\ge 3$, there exists ${\epsilon }_k>0$ such that if a graph $G$ satisfies ${\sum }_{0\le j\le k-1}{c}_{2j+1}(G-X)\le {\epsilon }_k|X|$ for all $X\subseteq V(G)$, then $G$ has a $\{P_2,P_{2k+1}\}$-factor, where $c_i(G-X)$ is the number of components $C$ of $G-X$ with $|V(C)|=i$. On the other hand, we construct infinitely many graphs $G$ having no $\{P_2,P_{2k+1}\}$-factor such that ${\sum }_{0\le j\le k-1}{c}_{2j+1}(G-X)\le \frac{32k+141}{72k-78}|X|$ for all $X\subseteq V(G)$.

18 pages, 1 figure

References in corpus (1)

• The existence of a path-factor without small odd paths