Bounds on threshold dimension and disjoint threshold coverings (abstract only)
P. Erdös, Edward T. Ordman, Yechezkel Zalcstein · 1985
The threshold dimension1 of a graph G is the smallest number of threshold graphs needed to cover the edges of G. If t(n) is the greatest threshold dimension of any graph of n vertices, we show that for some constant c, n-c √n log n < t(n) < n- √n + 1 We establish the same bounds for edge-disjoint coverings of graphs by threshold graphs. The results have applications to manipulating systems of simultaneous linear inequalities and to space bounds for synchronization problems2.