Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] A problem about Graph Partitions (guest post)

Expand Messages
  • GASARCH
    (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
    Message 1 of 1 , Feb 18, 2010
    • 0 Attachment
      (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
    Your message has been successfully submitted and would be delivered to recipients shortly.