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.

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

Linear Arboricity of cubic graphs is another example for your survey.


A nice paper where the structure of cubic planar graphs is exploited with enumerative purposes is the work of (Manuel Bodirsky, Mihyun Kang, Mike Löffler and Colin McDiarmid, Random cubic planar graphs, Random Structures and Algorithms 30 (2007), 78-94).

Indeed, the key point of the paper is how to decompose cubic graphs (not necessarily planar) in terms of 3-connected components (in this case, 3-connected cubic planar graphs).

In a similar direction, but with an stronger computational motivation, in (Manuel Bodirsky, Mihyun Kang and Clemens Gröpl, Generating unlabeled connected cubic planar graphs uniformly at random, Random Structures and Algorithms 32 (2008), 157-180) the authors explore more algorithmic aspects of this planar family (but now considering unlabelled structures, which makes the problem harder).

This two papers can show you a little how the use of generating functions has been successful in the context of planar graphs, and also some computational implications.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.