English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In a graph, a matching cut is an edge cut that is a matching. Matching Cut isthe problem of deciding whether or not a given graph has a matching cut, whichis known to be NP-complete even when restricted to bipartite graphs. It hasbeen proved that Matching Cut is polynomially solvable for graphs of diametertwo. In this paper, we show that, for any fixed integer $d\ge 3$, Matching Cutis NP-complete in the class of graphs of diameter $d$. This resolves an openproblem posed by Borowiecki and Jesse-J\'ozefczyk in [Matching cutsets ingraphs of diameter $2$, Theoretical Computer Science 407 (2008) 574-582].  We then show that, for any fixed integer $d\ge 4$, Matching Cut isNP-complete even when restricted to the class of bipartite graphs of diameter$d$. Complementing the hardness results, we show that Matching Cut ispolynomial-time solvable in the class of bipartite graphs of diameter at mostthree, and point out a new and simple polynomial-time algorithm solvingMatching Cut in graphs of diameter $2$.

A complexity dichotomy for Matching Cut in (bipartite) graphs of fixed diameter