How Many Disjoint 2--edge Paths Must a Cubic Graph Have?
Authors: Alexander Kelmans and Dhruv Mubayi
ABSTRACT
In this paper we show that every simple cubic graph
on $n$ vertices has a list of at least n/4
disjoint 2-edge paths and that this bound is sharp.
Our proof provides a polynomial time algorithm
for finding such a list in a simple cubic graph.
Keywords:
packing, 2--edge path, cubic graph, polynomial time algorithm.
DIMACS Home Page