Threshold tolerance graphs

DOI10.1002/JGT.3190120307MaRDI QIDQ3797238zbMATH OpenOpenAlexFDO

Authors Clyde l. Monma, Bruce Reed, William T. Trotter

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

algorithminterval graphsstrongly chordal graphsgraph recognitiongeneralization of threshold graphsinterval tolerance graphsThreshold tolerance graphs

Mathematics Subject Classification ID

Graph theory (05C99)

Recommendations

• scientific article; zbMATH DE number 4053682
• On recognition of threshold tolerance graphs and their complements
• Recognizing threshold tolerance graphs in O(n^2) time
• scientific article; zbMATH DE number 867635
• Recognizing Bipartite Tolerance Graphs in Linear Time

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• Incidence matrices and interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(23)

• -threshold and -tolerance chain graphs
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• scientific article; zbMATH DE number 4053682 (Why is no real title available?)
• scientific article; zbMATH DE number 29611 (Why is no real title available?)
• Towards a comprehensive theory of conflict-tolerance graphs
• Co-TT graphs and a characterization of split co-TT graphs
• Recognizing threshold tolerance graphs in O(n^2) time
• NeST graphs
• Recognition of linear and star variants of leaf powers is in P
• Query-Competitive Sorting with Uncertainty.
• Threshold graphs
• Linear-time recognition of double-threshold graphs
• Pairwise compatibility graphs: a survey
• Mock threshold graphs
• Min-orderable digraphs
• Lower bounds for leaf rank of leaf powers
• Query-competitive sorting with uncertainty
• Interval-like graphs and digraphs
• Double-threshold permutation graphs
• A recognition algorithm for adjusted interval digraphs
• On recognition of threshold tolerance graphs and their complements
• A vertex ordering characterization of simple-triangle graphs
• Neighborhood subtree tolerance graphs

This page was built for publication: Threshold tolerance graphs

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