Constant tolerance intersection graphs of subtrees of a tree (Q1764901)

Let \(G= (V,E)\) be a connected, finite, simple and loopless graphs. In this paper the structure of the intersection of a family of subsets of a set is investigated: the vertices of the graph are represented by the subsets of the family and adjacency is defined by a non-empty intersection of the corresponding subsets. Prime examples are interval graphs and chordal graphs, and a known classical result is the characterization of interval graphs by forbidden subgraphs. The authors generalize this by using tolerances introduced by Golumbic and Monma: each representing interval is assigned a positive real number, its tolerance, and two vertices are adjacent if the length of the intersection of their corresponding intervals exceeds the minimum of the two tolerances. This idea was used to formulate tolerance intersection graphs by the authors where \(G= (V,E)\) may be represented by a host tree \(T\) together with a family \(\{S_v\}_{v\in V}\) of subtrees of \(T\) and a tolerance \(t\) such that \(uv\in E\) iff \(|S_u\cap S_v|\geq t\). Then \(G\) has an \((h,s,t)\)-representation if moreover there exists a maximum degree of \(T\) at most \(h\) and a maximum degree of all \(S_v\subset T\) of at most \(s\). If no restrictions are imposed on \(h\), it is written \(h=\infty\), similarly it is written \(s= \infty\). In Section 2 concepts are introduced which are used in the paper. An example let be given here: If \(G_1\) and \(G_2\) and are two graphs with non-empty intersection \(G_1\cap G_2\), then \(G_1\cup G_2= (V_1\cup V_2, E_1\cup E_2)\) is the amalgamation of \(G_1\) and \(G_2\) along the common subgraph \(G_1\cap G_2\) (we also say: the amalgamation along the set of common vertices \(V_1\cap V_2\)). Furthermore, in Section 2 various kinds of representations are introduced and already known results from the literature are mentioned. (The class of \((h,s,t)\)-graphs is denoted by \([h,s,t]\) and being an \((h,s,t)\)-graph is a hereditary property which raises the problem of characterizing these graphs by forbidden induced subgraphs.) By definition, we have \[ \begin{aligned} [h,s,t]\subseteq [h^*,s,t]\quad &\text{for any }h^*\geq h,\\ [h,s,t]\subseteq [h,s^*,t]\quad &\text{for any }s^*\leq h\end{aligned} \] and this means that the class \([h,s,t]\) is monotone in the first two parameters \(h\) and \(s\). In Section 3 it is discussed in which ways chordal graphs can be represented as tolerance subtree graphs. Examples: -- A graph \(G= (V,E)\) is chordal iff it has an orthodox \((3,3,1)\)-representation (Theorem 1). -- Let \(G= (V,E)\) be an \((h,s,2)\)-graph with \(h\geq 3\). Then any induced cycle in \(G\) has length at most \(h\) (Theorem 2). Sections 4--6 contain the main results of the paper. Here the monotonicity of the various subclasses of \([h,s,t]\) with respect to the third parameter \(t\) is studied. If the maximum degree of the trees is fixed in the representations, then any graph can still be represented, provided the tolerance is chosen high enough (Section 4, Theorem 9). If both the tolerance and the maximum degree of the trees are fixed in the representation, then there are infinitely many minimal graphs that do not have a representation of the required type (Section 6, Theorems 19 and 21). In Section 5 it is discussed how to produce representations of larger graphs from smaller ones using amalgamation. The case of complete bipartite graphs is also crucial with respect to the question of representability or non-representability and therefore this is the topic of Section 7 (Theorem 23).