Importance: Medium ✭✭
Recomm. for undergrads: no
Posted by: fhavet
on: March 4th, 2013
Problem   Does every $ 3 $-connected cubic graph on $ 3k $ vertices admit a partition into $ k $ paths of length $ 2 $?

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.


[K1] Alexander K. Kelmans, Packing 3-vertex paths in 2-connected graphs

*[K2] Alexander K. Kelmans, On $ \Lambda $--Packing in 3--connected Graphs, RUTCOR Research Report 23--2005, Rutgers University. See also Packing 3-vertex Paths In Cubic 3-connected Graphs

* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.
More information about formatting options