The maximum cardinality cut problem in co-bipartite chain graphs.

A co-bipartite chain graph is a co-bipartite graph in which the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion. It is known that the maximum cardinality cut problem ( $${\textsc {MaxCut}}$$ ) is $${\textsc {NP}}{\text {-hard}}$$ in co-bipartite graphs (Bodlaender and Jansen, Nordic J Comput 7(2000):14-31, 2000). We consider $${\textsc {MaxCut}}$$ in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that $${\textsc {MaxCut}}$$ is polynomial time solvable in this graph class. [ABSTRACT FROM AUTHOR]