Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902912 | Discrete Mathematics | 2018 | 20 Pages |
Abstract
Mock threshold graphs are a simple generalization of threshold graphs that, like threshold graphs, are perfect graphs. Our main theorem is a characterization of mock threshold graphs by forbidden induced subgraphs. Other theorems characterize mock threshold graphs that are claw-free and that are line graphs. We also discuss relations with chordality and well-quasi-ordering as well as algorithmic aspects.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Richard Behr, Vaidy Sivaraman, Thomas Zaslavsky,