Recognition of graphs with threshold dimension two
Thomas Raschle, Klaus Simon · 1995
The recognition of threshold graphs, those graphs with threshold dimension one, is well understood and some linear time algorithms are known for this problem. On the other hand, Yannakakis proved that determining if the threshold dimension of a graph is less than or equal to k is NP-complete for all fixed k 3. Chv' atal and Hammer conjectured that the threshold dimension of a graph G = (V; E) equals the chromatic number of its derivated edge graph G = (V ; E ) where V = E and two edges ab and cd of G are adjacent in G if and only if ac; bd 62 E for distinct vertices a; b; c; d. Cozzens and Leibowitz disproved this conjecture for graphs whose chromatic number of G is greater or equal to four. In this paper we show that Chv' atal and Hammer's conjecture is true in case of G bipartite. We also present an O(jEj 2 ) algorithm which either computes an edge cover consisting of the edges of two threshold graphs or decides that such a cover does not exist. In partic...