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

An (h,s,t)(h,s,t)-representation of a graph GG consists of a collection of subtrees of a tree TT, where each subtree corresponds to a vertex in GG, such that (i) the maximum degree of TT is at most hh, (ii) every subtree has maximum degree at most ss, (iii) there is an edge between two vertices in the graph GG if and only if the corresponding subtrees have at least tt vertices in common in TT. The class of graphs that have an (h,s,t)(h,s,t)-representation is denoted by [h,s,t][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][h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1][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][h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t][h,2,t] by three main parameters: hh, tt 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][h,2,t] and orthodox-[h,2,t][h,2,t] graphs for varied values of hh and tt.