Equivalences and the complete hierarchy of intersection graphs of paths in a tree

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted by h,s,t]. It is well known that the class of chordal graphs corresponds to the class 3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-3, 3, 1] graphs defined below.In this paper, we investigate the class of h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The h,2,1] graphs are also known as path graphs F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211-227] or VPT graphs M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151-159], and h,2,2] graphs are known as the EPT graphs. We consider variations of h,2,t] by three main parameters: h, t and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, h,2,t] and orthodox-h,2,t] graphs for varied values of h and t.