Path factors in cubic graphs
Ken‐ichi Kawarabayashi, Haruhide Matsuda, Yoshiaki Oda, Katsuhiro Ota · Journal of Graph Theory · 2002
Abstract Let ℱ be a set of connected graphs. An ℱ‐factor of a graph is its spanning subgraph such that each component is isomorphic to one of the members in ℱ. Let Pk denote the path of order k. Akiyama and Kano have conjectured that every 3‐connected cubic graph of order divisible by 3 has a {P3}‐factor. Recently, Kaneko gave a necessary and sufficient condition for a graph to have a {P3, P4, P5}‐factor. As a corollary, he proved that every cubic graph has a {P3, P4, P5}‐factor. In this paper, we prove that every 2‐connected cubic graph of order at least six has a {Pk ∣ k ≥ , 6}‐factor, and hence has a {P3, P4}‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 188–193, 2002; DOI 10.1002/jgt.10022