Насколько сложно определить существование красно-синего идеального соответствия?

Задача двухцветного идеального сопоставления состоит в том, чтобы решить, имеет ли граф раскраску с двумя цветами, чтобы у каждого узла был ровно один сосед того же цвета, что и он сам. Шефер доказал, что задача является NP-полной . Он остается NP-полным даже для плоских кубических графов.

Меня интересует вариант, в котором мы хотим решить, будет ли входной граф раскрашиваться двумя цветами, чтобы у каждого узла был ровно один сосед, окрашенный в разные цвета. Я называю это красно-синей проблемой идеального соответствия. Я не знаю, является ли это известной проблемой.

Насколько сложно определить существование красно-синего идеального соответствия?

Как отметил Михаил, в литературе проблема называлась Perfect Matching Cut. Доказано, что он NP-завершен в следующей статье (см. Теорему 1 на стр. 5) с сокращением от монотонного 1-в-3-SAT:

Пинар Хеггернес, Ян Арне Тель. Разбиение графов на обобщенные доминирующие множества.