Towards a comprehensive theory of conflict-tolerance graphs

DOI10.1016/j.dam.2011.12.026zbMath1292.05219OpenAlexW2030634141MaRDI 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

treesinterval graphsintersection graphsgraph representationsminimal forbidden subgraphs

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Dyadic representations of graphs

Cites Work

• 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
• 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