Tolerance intersection graphs on binary trees with constant tolerance 3
type: Item
instance of: scholarly article
title: Tolerance intersection graphs on binary trees with constant tolerance 3
zbMATH Open document ID: 0947.05055
DOI: 10.1016/S0012-365X(99)00231-9
author: Robert E. Jamison
author: Henry Martyn Mulder
published in: Discrete Mathematics
publication date: 2000-11-12T00:00:00Z
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.
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1439828
zbMATH Keywords: intersection graphs
zbMATH Keywords: binary trees
zbMATH Keywords: tolerance
zbMATH Keywords: chordal graph
zbMATH Keywords: subtree representation
reviewed by: E. Keith Lloyd
MaRDI profile type: Publication
Wikidata QID: Q127674034
full work available at URL: s0012-365x(99)00231-9
OpenAlex ID: W2095263228
Recommended article: Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2
Recommended article: Constant tolerance intersection graphs of subtrees of a tree
Recommended article: Constant tolerance representations of graphs in trees
Recommended article: General results on tolerance intersection graphs
Recommended article: Q4873748
Recommended article: Constant threshold intersection graphs of orthodox paths in trees
Recommended article: A New Intersection Model and Improved Algorithms for Tolerance Graphs
Recommended article: Q4862906
Recommended article: Q3322150
description: scientific article; zbMATH DE number 1439828