6
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Perhaps you should write the survey that apparently does not yet exist... :-) $\endgroup$ Feb 2, 2014 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$ Feb 3, 2014 at 9:07
  • $\begingroup$ That's a strong conjecture! I am not thinking of a counterexample off-hand... $\endgroup$ Feb 3, 2014 at 12:24
  • $\begingroup$ Could you add references for those NP-complete cases you mention? $\endgroup$ Feb 26, 2014 at 9:01

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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