Helly EPT graphs on bounded degree trees: Characterization and recognition

Abstract

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.