Two characterisations of minimal triangulations of 2K2-free graphs

Abstract2K2-free graphs do not contain the complement of the chordless cycle on four vertices (2K2) as induced subgraph. A triangulation H of a graph G is a chordal graph that is obtained by adding edges. If no proper subgraph of H is a triangulation of G, H is a minimal triangulation of G. We will show that the split graphs are exactly the minimal triangulations of 2K2-free graphs. This result implies a characterisation of the set of minimal triangulations of a single 2K2-free graph by special maximal independent sets. As an application, we will give a linear-time algorithm for computing the treewidth of co-chordal graphs