# Cubic graphs decompositions

There are many interesting computational problems related to connected cubic graph decomposition. For instance, decomposition of cubic graph into a perfect matching and a connected 2-factor (NP-complete), decomposition of cubic graph into a perfect matching and an even 2-factor (NP-complete), decomposition of cubic graph into a three perfect matchings (NP-complete), and decomposition of cubic graph into two equal-size trees (NP-complete).

I am looking for a survey paper or book chapter on connected cubic graph decompositions.

It would be very nice if the references are focused on the computational aspects of cubic graph decompositions.

Motivation: These graph decompositions can be defined as partition of the edge set $E$ of connected cubic graph $G(V, E)$ into two sets $E_1$ and $E_2$ such that each one satisfies some graph property. This kind of cubic graph decomposition exists for infinite class of connected cubic graphs and there is infinite class of connected cubic graphs without such decomposition. I conjecture that every such decomposition of connected cubic graphs is NP-complete.

• Perhaps you should write the survey that apparently does not yet exist... :-) – Joseph O'Rourke Feb 2 '14 at 15:24
• @JosephO'Rourke Good idea. Are you aware of polynomial-time decomposition problem (of connected cubic graph) of type I mentioned in my motivation? – Mohammad Al-Turkistany Feb 3 '14 at 9:07
• That's a strong conjecture! I am not thinking of a counterexample off-hand... – Joseph O'Rourke Feb 3 '14 at 12:24
• Could you add references for those NP-complete cases you mention? – Anthony Labarre Feb 26 '14 at 9:01