Towards a comprehensive theory of conflict-tolerance graphs

DOI10.1016/j.dam.2011.12.026zbMath1292.05219MaRDI QIDQ1759850

Robert E. Jamison

Publication date: 22 November 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.12.026

zbMATH Keywords

trees; interval graphs; intersection graphs; graph representations; minimal forbidden subgraphs

Mathematics Subject Classification ID

05C05: Trees

05C75: Structural characterization of families of graphs

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Dyadic representations of graphs

Cites Work

• Maximum weight independent sets and cliques in intersection graphs of filaments
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• \(\phi\)-threshold and \(\phi\)-tolerance chain graphs
• The edge intersection graphs of paths in a tree
• Tolerance graphs
• Tree representations of graphs
• Equivalences and the complete hierarchy of intersection graphs of paths in a tree
• Intersection models of weakly chordal graphs
• Edge and vertex intersection of paths in a tree
• On the chromatic number of multiple interval graphs and overlap graphs
• Triangulated edge intersection graphs of paths in a tree
• A characterization of Robert's inequality for boxicity
• Comparability graphs and intersection graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Intersection representation of complete unbalanced bipartite graphs
• Maximum independent set and maximum clique algorithms for overlap graphs
• Constant tolerance intersection graphs of subtrees of a tree
• Tolerance intersection graphs on binary trees with constant tolerance 3
• Subtree filament graphs are subtree overlap graphs
• The \(k\)-edge intersection graphs of paths in a tree
• Representing edge intersection graphs of paths on degree 4 trees
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• Efficient algorithms for finding maximum cliques of an overlap graph
• Interval Graphs with Containment Restrictions
• Threshold tolerance graphs
• Representations of chordal graphs as subtrees of a tree
• General results on tolerance intersection graphs
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Set intersection representations for almost all graphs
• Archimedean ϕ ‐tolerance graphs
• What Is between Chordal and Weakly Chordal Graphs?
• Rank‐tolerance graph classes
• The Representation of a Graph by Set Intersections
• A short proof of Sperner's lemma
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item