Helly EPT graphs on bounded degree trees: characterization and recognition

LILIANA ALCÓN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI

DISCRETE MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2018 vol. 340 p. 2798 - 2806

0012-365X

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, thefamily 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 subgraphsfor [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 notnecessary to increase the maximum degree of the host tree. In addition, we give an efficientalgorithm to recognize Helly [h, 2, 2] graphs based on their decomposition by maximalclique separators.