The lexicographic method for the threshold cover problem (Q5896104)

In this paper, the authors consider finite, undirected graphs that do not contain loops or parallel edges. For a positive integer \(t\), let \(P_t\) and \(C_t\) be the path and cycle on \(t\) vertices, respectively. Moreover, let \(t\cdot K_2\) be the graph which contains \(t\) components such that each component has two vertices. A graph is said to be a threshold graph, if it does not contain an induced subgraph that is isomorphic to \(2\cdot K_2\), \(P_4\) or \(C_4\). A graph \(H\) is said to have a threshold cover of size \(k\), if \(E(H)\) can be presented as a union of \(k\) threshold subgraphs. In their work on this topic, for a given graph \(G\) \textit{V. Chvatal} and \textit{P. L. Hammer} [Ann. Discrete Math. 1, 145--162 (1977; Zbl 0384.90091)] defined an auxiliary graph \(G^\prime\), such that any threshold cover of \(G\) must have size at least \(\chi(G^\prime)\). Here \(\chi\) denotes the chromatic number of the graph under consideration. The main goal of this paper is to give a new, short and self-contained proof of a result of \textit{T. Raschle} and \textit{K. Simon} [in: Proceedings of the 27th annual ACM symposium on the theory of computing, STOC '95. Las Vegas, NV, USA, May 29 -- June 1, 1995. New York, NY: ACM. 650--661 (1995; Zbl 0920.05063)], which states that a graph can be covered with two threshold graphs if and only if its auxiliary graph \(G^\prime\) is bipartite. The proof given by the authors implies a recognition algorithm with \(O(|E(G)|^2)\) running-time, which returns a certificate that the input graph has a threshold cover of size \(2\). For the entire collection see [Zbl 1435.68020].