(Guest post from Richard Taylor who requests information on a problem.)
The following graph partition problem arises in connection with studies
I am doing on a particular dynamical systems problem. I wonder if there
are any complexity results on it. Given a 3-regular graph, can the
vertex set be partitioned into 2 sets in such a way that the induced
subgraphs formed each have vertices of degree at least 2? Could this be
NP complete? There are a few results on vertex partitions I have found
in the literature - but none quite like this.
First Request from Bill G:
In the past I have posted on problems and have
had comments tell me that its well known or falls out easily from
some theory, but then not give me a reference or proof sketch. Please, if
you are going to say its known, give a reference or proof sketch.
Posted By GASARCH to Computational Complexity
at 2/18/2010 08:54:00 AM