Two-colorable perfect matching problem is to decide whether a graph has coloring with two colors such that each node has exactly one neighbor the same color as itself. The problem was proven to be NP-complete by Schaefer. It remains NP-complete even for planar cubic graphs.

I am interested in a variant where we want to decide whether input graph has coloring with two colors such each node has exactly one neighbor colored differently from itself. I call this Red-Blue perfect matching problem. I don't know whether this is a known problem.

How hard is deciding the existence of Red-Blue perfect matching?

  • 1
    $\begingroup$ Another way of stating this problem would be to ask whether the given graph has a perfect matching which is also a cut. $\endgroup$ – Mikhail Rudoy May 4 at 7:30

As Mikhail noted, the problem was called Perfect Matching Cut in literatures. It was proved to be NP-complete in the following paper (see Theorem 1 on page 5), with a reduction from monotone 1-in-3-SAT:

Pinar Heggernes, Jan Arne Telle. Partitioning Graphs Into Generalized Dominating Sets.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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