Helly EPT graphs on bounded degree trees: Characterization and recognition

The edge-intersection graph of a family of paths on a host tree is called an $EPT$ graph. When the tree has maximum degree $h$, we say that the graph is $h,2,2]$. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly $h,2,2]$. In this paper, we present a family of $EPT$ graphs called gates which are forbidden induced subgraphs for $h,2,2]$ graphs. Using these we characterize by forbidden induced subgraphs the Helly $h,2,2]$ graphs. As a byproduct we prove that in getting a Helly $EPT$-representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly $h,2,2]$ graphs based on their decomposition by maximal clique separators.