Tolerance intersection graphs on binary trees with constant tolerance 3

DOI10.1016/S0012-365X(99)00231-9MaRDI QIDQ1974525zbMATH OpenOpenAlexWikidataFDO

Authors Robert E. Jamison, Henry Martyn Mulder

Publication date 12 November 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00231-9

zbMATH Keywords

binary treeschordal graphintersection graphssubtree representationtolerance

Mathematics Subject Classification ID

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

Review text

A 3-subtree-representation \((T,{\mathcal S})\) of a connected graph \(G= (V,E)\) consists of a binary host tree \(T\) and a family of subtrees \({\mathcal S}= \{S_u\mid u\in V\}\) of \(T\) such that \(uv\in E\) if and only if \(|S_u\cap S_v|\geq 3\). A graph \(G\) is representable if it has such a representation. By imposing additional conditions, the authors consider two subclasses of representable graphs called ORTHODOX and FAITHFUL. They show that \(\text{ORTHODOX} \subset \text{FAITHFUL} \subset \text{REPRESENTABLE},\) where the inclusions are strict. Further results are obtained in particular for complete bipartite graphs and \(\Theta\)-graphs.

Recommendations

• Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2
• Constant tolerance intersection graphs of subtrees of a tree
• Constant tolerance representations of graphs in trees
• General results on tolerance intersection graphs
• scientific article; zbMATH DE number 867635
• Constant threshold intersection graphs of orthodox paths in trees
• A new intersection model and improved algorithms for tolerance graphs
• A new intersection model and improved algorithms for tolerance graphs
• Publication:4862906
• scientific article; zbMATH DE number 3853140

Cited in

(20)

• Equivalences and the complete hierarchy of intersection graphs of paths in a tree
• Intersection models of weakly chordal graphs
• NeST graphs
• Towards a comprehensive theory of conflict-tolerance graphs
• Constant tolerance intersection graphs of subtrees of a tree
• Dyadic representations of graphs
• Constant threshold intersection graphs of orthodox paths in trees
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2
• Intersection graphs of orthodox paths in trees
• The k-edge intersection graphs of paths in a tree
• Representing edge intersection graphs of paths on degree 4 trees
• Constant tolerance representations of graphs in trees
• \(K_{1,3}\)-subdivision tolerance representations of cycles
• Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
• Approximation algorithms for intersection graphs
• Inductive graph invariants and approximation algorithms
• What Is between Chordal and Weakly Chordal Graphs?
• Recognizing vertex intersection graphs of paths on bounded degree trees
• Generalized disk graphs

This page was built for publication: Tolerance intersection graphs on binary trees with constant tolerance 3

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