Si-zhong ZHOU, Zhi-ren SUN, Hong-xia LIU
A spanning subgraph F of a graph G is called a path factor of G if each component of F is a path. A P≥k-factor means a path factor with each component having at least k vertices, where k≥2 is an integer. Bazgan, Benhamdine, Li and Wozniak [C. Bazgan, A. H. Benhamdine, H. Li, M. Wozniak, Partitioning vertices of 1-tough graph into paths, Theoret. Comput. Sci. 263(2001)255--261.] obtained a toughness condition for a graph to have a P≥3-factor. We introduce the concept of a P≥k-factor deleted graph, that is, if a graph G has a P≥k-factor excluding e for every e∈ E(G), then we say that G is a P≥k-factor deleted graph. In this paper, we show four sufficient conditions for a graph to be a P≥3-factor deleted graph. Furthermore, it is shown that four results are best possible in some sense.