The existence of path-factor covered graphs (Q2107737)

A \(P_{\geq k}\)-factor of a graph \(G\) is a spanning subgraph with the property that each of its components is isomorphic to a path of order at least \(k\). A \(P_{\geq k}\)-factor covered graph is a graph \(G\) with the property that there is a \(P_{\geq k}\)-factor containing \(e\) for every edge \(e\) of \(G\). This paper gives several sufficient conditions for a graph to be \(P_{\geq 2}\)-factor covered or \(P_{\geq 3}\)-factor covered. To state them, let first \(i(G)\) be the number of isolated vertices of \(G\), and let \[I(G) = \min \Big\{ \frac{|S|}{i(G-S)} \,:\, S \subseteq V(G), i(G - S) \geq 2 \Big\}\] be its isolated toughness (\(I(G) = \infty\) for complete graphs). The following statements hold: \begin{itemize} \item Every connected claw-free graph of minimum degree at least \(2\) is \(P_{\geq 2}\)-factor covered. \item Every connected graph \(G\) with at least two vertices and \(I(G) > \frac23\) is \(P_{\geq 2}\)-factor covered. \item Every connected claw-free graph of minimum degree at least \(3\) is \(P_{\geq 3}\)-factor covered. \item Every 3-connected planar graph is \(P_{\geq 3}\)-factor covered. \end{itemize}