Constant tolerance intersection graphs of subtrees of a tree

DOI10.1016/j.disc.2004.04.017zbMath1061.05079OpenAlexW2068177175MaRDI QIDQ1764901

Henry Martyn Mulder, Robert E. Jamison

Publication date: 22 February 2005

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

Full work available at URL: https://doi.org/10.1016/j.disc.2004.04.017

zbMATH Keywords

Chordal graphToleranceIntersection graph\(k\)-simplicial vertexRegular treeSubtree representation

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items

Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2 ⋮ What Is between Chordal and Weakly Chordal Graphs? ⋮ Helly EPT graphs on bounded degree trees: characterization and recognition ⋮ Intersection graphs of orthodox paths in trees ⋮ Constant threshold intersection graphs of orthodox paths in trees ⋮ A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree ⋮ The vertex leafage of chordal graphs ⋮ Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs ⋮ The \(k\)-edge intersection graphs of paths in a tree ⋮ Representing edge intersection graphs of paths on degree 4 trees ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Dyadic representations of graphs ⋮ Equivalences and the complete hierarchy of intersection graphs of paths in a tree ⋮ Recognizing vertex intersection graphs of paths on bounded degree trees ⋮ Intersection models of weakly chordal graphs ⋮ Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating Whitney sums and matchings in trees. II
• On rigid circuit graphs
• The edge intersection graphs of paths in a tree
• Tolerance graphs
• Edge and vertex intersection of paths in a tree
• Triangulated edge intersection graphs of paths in a tree
• Intersection graphs of paths in a tree
• Alternating Whitney sums and matchings in trees. 1
• Connectivity threshold for random chordal graphs
• Intersection representation of complete unbalanced bipartite graphs
• A characterisation of rigid circuit graphs
• Graphs of small dimensions
• Tolerance intersection graphs on binary trees with constant tolerance 3
• 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
• Representations of chordal graphs as subtrees of a tree
• Topics in Intersection Graph Theory
• Set intersection representations for almost all graphs
• Onp-intersection representations
• Sur deux propriétés des classes d'ensembles