Multithreshold graphs
Robert E. Jamison, Alan Sprague · Journal of Graph Theory · 2020
Abstract Multithreshold graphs are defined in terms of a finite sequence of real thresholds that break the real line into a set of regions, alternating between NO and YES. If real ranks can be assigned to the vertices of a graph in such a way that two vertices are adjacent iff the sum of their ranks lies in a YES region, then that graph is a multithreshold graph with respect to the given set of thresholds. If a graph can be represented with k or fewer thresholds, then it is k‐threshold. The case of one threshold is the classical case introduced by Chvátal and Hammer. In this paper, we show for every graph G, there is a k such that G is k‐threshold, and we exhibit graphs for which the required number of thresholds is linear in the order of the graph.