Decomposing Cubic Graphs into Connected Subgraphs of Size Three

Let S be the set of connected graphs with three edges ( S contains the triangle, the claw, and the path on 4 vertices). We study the problem of partitioning the edge set of a graph G into graphs taken from S or, more generally, from any non-empty subset S ‘ of S. The problem is known to be NP-complete for any possible choice of S ‘ in general graphs. In this talk, we assume that the input graph is cubic, and study the computational complexity of the problem of partitioning its edge set for any choice of S ’. We identify all polynomial and NP-complete problems in that setting, and give graph-theoretic characterizations of S ‘-decomposable cubic graphs in some cases.

(joint work with Guillaume Fertin, Anthony Labarre, Romeo Rizzi and Irena Rusu)