On the recognition and characterization of M-partitionable proper interval graphs

For a symmetric {0, 1, ⋆ }-matrix M of size m, a graph G is said to be M-partitionable, if its vertices can be partitioned into sets V1, V2, . . . , Vm, such that two parts Vi, Vj are completely adjacent if Mi,j = 1, and completely non-adjacent if Mi,j = 0 (Vi is considered completely adjacent to itself if it induces a clique, and completely non-adjacent if it induces an independent set). The complexity problem (or the recognition problem) for a matrix M asks whether the M-partition problem is polynomial-time solvable or NP-complete. The characterization problem for a matrix M asks if all M-partitionable graphs can be characterized by the absence of a finite set of forbidden induced subgraphs. These forbidden induced subgraphs are called obstructions to M. In the literature, many results were obtained by restricting the input graphs. In this thesis, we survey these results when the questions are restricted to the class of perfect graphs. We then study the recognition problem and the characterization problem when the inputs are restricted to proper interval graphs. The recognition problem can be solved by an existing algorithm, but we simplify its proof of correctness. As our main result, we prove that all the matrices of size 3 and size 4 with constant diagonal, have finitely many minimal proper interval obstructions. We also obtain partial results about matrices of arbitrary size if they have a zero diagonal.