Tolerance intersection graphs on binary trees with constant tolerance 3 (Q1974525): Difference between revisions

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.