Graph-theory open problems

Partition of a cubic 3-connected graphs into paths of length 2.

Medium ★★ Graph Theory » Basic Graph Theory » Paths
Author: Kelmans, Alexander K.— posted by fhavet on 2013-03-04

Status open medium confidence

The conjecture—that every 3-connected cubic graph on $3k$ vertices admits a partition into $k$ paths of length 2 (a $P_3$-factor)—remains open. Prior to the OPG posting, Kelmans established several equivalent reformulations and showed the conjecture implies Reed’s dominating conjecture for cubic 3-connected graphs, but no proof or disproof exists. Searches through 2026 found no post-2013 paper that resolves the problem.

Reviewer notes. The problem is also attributed to Akiyama and Kano (1985 conjecture). All relevant arXiv papers found (0910.2766, 0801.1239, 0711.3871, 0712.4151, 0910.4681) predate the 2013 posting. Two possibly relevant post-2013 papers were identified — 'On maximum P3-packing in claw-free subcubic graphs' (J. Comb. Opt., 2021) and 'Packing 2- and 3-stars into cubic graphs' (ScienceDirect, 2023) — but both were behind paywalls (HTTP 403) and no arXiv versions were found; they also appear to address different graph classes (claw-free subcubic vs. stars). Confidence is medium rather than high because those inaccessible papers could in principle contain relevant partial results.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 02) (web search enabled).

Problem. Does every $ 3 $ -connected cubic graph on $ 3k $ vertices admit a partition into $ k $ paths of length $ 2 $ ?

Discussion

More generally, the following question is posed. Problem Does every $ 3 $ -connected cubic graph on at least $ 3k $ vertices contain $ k $ pairwise vertex-disjoint paths of length $ 2 $ ? In [K1], Kelmans gave a construction that provided infi nitely many 2-connected graphs for which the above statement is false.

Bibliography