It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.

}, keywords = {Graph algorithms, Maximum cut, Proper interval graph}, issn = {0020-0190}, doi = {https://doi.org/10.1016/j.ipl.2017.01.007}, url = {https://www.sciencedirect.com/science/article/pii/S0020019017300133}, author = {Arman Boyac{\i} and Ekim, Tinaz and Mordechai Shalom} } @article {1510, title = {Graphs of edge-intersecting and non-splitting paths}, journal = {Theoretical Computer Science}, volume = {629}, year = {2016}, pages = {40-50}, abstract = {The families of Edge Intersection Graphs of Paths in a tree (resp. in a grid) EPT (resp. EPG) are well studied graph classes. Recently we introduced the class of graphs of Edge-Intersecting and Non-Splitting Paths in a Tree (ENPT) [5]. In this model, two vertices are adjacent if they represent two intersecting paths of a tree whose union is also a path. In this study we generalize this graph class by allowing the host graph to be an arbitrary graph. These are the graphs of Edge-Intersecting and Non-Splitting Paths ENP. Although the Edge Intersection Graphs of Paths in an arbitrary graph includes all graphs, we show that this is not the case for ENP. We also show that the class ENP coincides with the family of graphs of Edge-Intersecting and Non-Splitting Paths in a Grid (ENPG). Following similar studies for EPG graph class, we study the implications of restricting the number of bends of the individual paths in the grid. We show that such a restriction restricts the graph class. Specifically, by restricting the number of bends one gets an infinite sequence of classes such that every class is properly included in the next one.

}, issn = {0304-3975}, doi = {https://doi.org/10.1016/j.tcs.2015.10.004}, url = {https://www.sciencedirect.com/science/article/pii/S0304397515008750} }