Threshold Dimension of Split-permutation Graphs

Abstract

The threshold dimension of a graph is the minimum number of threshold subgraphs needed to cover its edges. In this work, we present a new characterization of split-permutation graphs and prove that their threshold dimension is at most two. As a consequence, we obtain a structural characterization of threshold graphs.