Matching (Multi)Cut: Algorithms, Complexity, and Enumeration

Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins +1

A matching cut of a graph is a partition of its vertex set in two such that no vertex has more than one neighbor across the cut. The Matching Cut problem asks if a graph has a matc…