Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius

Felicia Lucke, Daniël Paulusma, Bernard Ries

The (Perfect) Matching Cut problem is to decide if a graph $G$ has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of $G$. Both Matching Cut and Perfe…