Threshold tolerance graphs

DOI10.1002/jgt.3190120307zbMath0652.05059MaRDI QIDQ3797238

Clyde l. Monma, William T. jun. Trotter, Bruce A. Reed

Publication date: 1988

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190120307

zbMATH Keywords

algorithm; interval graphs; strongly chordal graphs; graph recognition; interval tolerance graphs; generalization of threshold graphs; Threshold tolerance graphs

Mathematics Subject Classification ID

05C99: Graph theory

Related Items

Unnamed Item, Min-Orderable Digraphs, Query-Competitive Sorting with Uncertainty., Linear-time recognition of double-threshold graphs, Recognition of linear and star variants of leaf powers is in P, On recognition of threshold tolerance graphs and their complements, \(\phi\)-threshold and \(\phi\)-tolerance chain graphs, NeST graphs, Towards a comprehensive theory of conflict-tolerance graphs, A vertex ordering characterization of simple-triangle graphs, Neighborhood subtree tolerance graphs, Double-threshold permutation graphs, Co-TT graphs and a characterization of split co-TT graphs, A recognition algorithm for adjusted interval digraphs, Query-competitive sorting with uncertainty, Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time, Pairwise Compatibility Graphs: A Survey

Cites Work

• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• A Characterization of Comparability Graphs and of Interval Graphs