Constant tolerance intersection graphs of subtrees of a tree

A chordal graph is the intersection graph of a family of subtrees of a host tree. In this paper we generalize this. A graph G=(V,E) has an (h,s,t)-representation if there exists a host tree T of maximum degree at most h, and a family of subtrees {Sv}v∈V of T, all of maximum degree at most s, such that uv∈E if and only if |Su∩Sv|≥t. For given h,s, and t, there exist infinitely many forbidden induced subgraphs for the class of (h,s,t)-graphs. On the other hand, for fixed h≥s≥3, every graph is an (h,s,t)-graph provided that we take t large enough. Under certain conditions representations of larger graphs can be obtained from those of smaller ones by amalgamation procedures. Other representability and non-representability results are presented as well.

• View at Publisher
• View at Scopus
• View at Web of Science