[Computational Complexity] A problem about Graph Partitions (guest post)
- (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