@inproceedings{add3af9651a94b4db4f3b785920823ea,
title = "Characterization and Linear-Time Recognition of Paired Threshold Graphs",
abstract = "In a paired threshold graph, each vertex has a weight, and two vertices are adjacent if and only if their weight sum is large enough and their weight difference is small enough. It generalizes threshold graphs and unit interval graphs, both very well studied. We present a vertex ordering characterization of this graph class, which enables us to prove that it is a subclass of interval graphs. Further study of clique paths of paired threshold graphs leads to a simple linear-time recognition algorithm for the graph class.",
keywords = "(Paired) threshold graph, (Unit) interval graph, Broom ordering, Clique path, Interval model, Interval ordering, Umbrella ordering",
author = "Yixin Cao and Guozhen Rong and Jianxin Wang",
note = "Funding Information: The full version of this paper, available at arXiv:1909.13029, contains all the proofs, some of which are omitted from this version due to the lack of space. Y. Cao?Supported by RGC grants 15201317 and 15226116, and NSFC grant 61972330. G. Rong and J. Wang?Supported by NSFC grants 61828205 and 61672536. Funding Information: The full version of this paper, available at arXiv:1909.13029, contains all the proofs, some of which are omitted from this version due to the lack of space. Y. Cao—Supported by RGC grants 15201317 and 15226116, and NSFC grant 61972330. G. Rong and J. Wang—Supported by NSFC grants 61828205 and 61672536. Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020 ; Conference date: 24-06-2020 Through 26-06-2020",
year = "2020",
doi = "10.1007/978-3-030-60440-0_24",
language = "English",
isbn = "9783030604394",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "298--309",
editor = "Isolde Adler and Haiko M{\"u}ller",
booktitle = "Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers",
address = "Germany",
}