Mock Threshold Graphs

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.

arXiv comment26 pp., 10 figures. V2: 36 pp., 10 figures (improved), added contractibility & remarks