Packing Three-Vertex Paths in $2$-Connected Cubic Graphs

Abstract

We show that every $2$-connected cubic graph of order $n>8$ admits a $P_3$-packing of at least $\frac{9n}{11}n$ vertices. The proof is constructive, implying an $O(M(n))$ time algorithm for constructing such a packing, where $M(n)$ is the time complexity of the perfect matching problem for $2$-connected cubic graphs.