The lexicographic method for the threshold cover problem

DOI10.1007/978-3-030-39219-2_4MaRDI QIDQ5896104zbMATH OpenOpenAlexFDO

Authors Mathew C. Francis, Dalu Jacob

Publication date 21 July 2020

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.05819

zbMATH Keywords

chain graph coverlexicographic methodthreshold cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Threshold graphs are a class of graphs that have many equivalent definitions and have applications in integer programming and set packing problems. A graph is said to have a threshold cover of size $k$ if its edges can be covered using $k$ threshold graphs. Chv'atal and Hammer, in 1977, defined the threshold dimension $mathrmth(G)$ of a graph $G$ to be the least integer $k$ such that $G$ has a threshold cover of size $k$ and observed that $mathrmth(G)geqchi(G^{\ast })$, where $G^{\ast }$ is a suitably constructed auxiliary graph. Raschle and Simon~[Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC '95, pages 650--661, 1995] proved that $mathrmth(G)=chi(G^{\ast })$ whenever $G^{\ast }$ is bipartite. We show how the lexicographic method of Hell and Huang can be used to obtain a completely new and, we believe, simpler proof for this result. For the case when $G$ is a split graph, our method yields a proof that is much shorter than the ones known in the literature.

Review text

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].

Recommendations

• scientific article; zbMATH DE number 1263242
• The lexicographic method for the threshold cover problem
• Strict 2-threshold graphs
• Some properties of 2-threshold graphs
• Bounds on Threshold Dimension and Disjoint Threshold Coverings
• An \(O(n^ 3)\) recognition algorithm for bithreshold graphs
• Total matchings and total coverings of threshold graphs
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Bipartite Coverings of Graphs
• On 3-colorings of bipartitep-threshold graphs

Cited in

(5)

• Representing graphs as the intersection of cographs and threshold graphs
• Bounds on Threshold Dimension and Disjoint Threshold Coverings
• Some properties of 2-threshold graphs
• scientific article; zbMATH DE number 1263242 (Why is no real title available?)
• The lexicographic method for the threshold cover problem

This page was built for publication: The lexicographic method for the threshold cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896104)