06078952

j

06078952 Eaton, Nancy Faubert, Glenn Caterpillar tolerance representations. Bull. Inst. Comb. Appl. 64, 109-117 (2012). 2012 The Institute of Combinatorics and its Applications, Winnipeg EN tolerance graphs intersection graphs of subtrees of a path Summary: Various families of tolerance graphs of subtrees for specific families of host trees and tolerance functions have been successfully characterized. For example, chordal graphs are intersection (tolerance 1) graphs of subtrees of general trees. Intersection graphs of subtrees of a path are those that are chordal and do not contain an asteroidal triple. We denote by $\text{cat}[h, t]$ the tolerance graphs of subtrees where the host is a caterpillar of maximum degree $h$ and the tolerance function is the constant $t$ for all vertices. We give a characterization involving asteroidal triples with no simplicial vertices for the equivalent families $\text{cat}[3,1]$, $\text{cat}[3,2]$, and $\text{cat}[h,1]$ for all $h\ge 3$. We also prove that $\text{cat}[4,2]= \text{cat}[3,3]$ and that $\text{cat}[h,2]\subseteq\text{cat}[h- 1,3]$ for $h\ge 5$.