The NP-completeness conjecture for recognizing 2-divisible graphs
Statement
Let be a graph. It is 2-divisible if, for every induced subgraph of , the vertex set can be partitioned into sets and such that
The NP-completeness conjecture. It is NP-complete to determine whether a graph is 2-divisible.
The conjecture concerns the computational complexity of recognizing 2-divisible graphs; no resolution is given in the source.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.