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?