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.
Citation
Adrian Kosowski, Pawel Zylinski. Packing Three-Vertex Paths in \(2\)-Connected Cubic Graphs[J], Ars Combinatoria, Volume 089. 95-113. .