Thinness 2 conditioned to co-bipartition orderings

Abstract

In this work, we focus on the characterization by forbidden patterns of the classes of graphs defined by their thinness, a graph width parameter defined by Mannino, Oriolo, Ricci, and Chandran. Specifically, we work on a minimal forbidden pattern characterization of the class of conditioned 2-thin co-bipartite graphs. To reach such a characterization, we define the notions of hinge order and conditioned 2-thin representation. The first concept defines a vertex ordering based on its 2-thin order and partition, while the second introduces restrictions on that order. We identify a general property of graphs with thinness at most 2, showing that given a hinge order associated with a 2-thin representation, splitting that order at any point to define two classes—where the first follows a canonical interval order and the second follows the reverse of such an ordering—yields another 2-thin representation with the same hinge order. Using this result, we prove that for any conditioned 2-thin co-bipartite graph, there exists a 2-thin representation with a conditioned hinge order such that each class forms a clique. Additionally, we obtain that the edges between the two classes induce an interval bigraph.