Characterizing local EPT graphs on bounded degree trees

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

Montevideo

Workshop; ALIO/EURO Workshop on Applied Combinatorial Optimization series; 2014

An undirected graph G is called an EPT graph if it is the edge intersection graph of a family of paths in a tree. We call G a local EPT graph if it is the EPT graph of a collection of paths P which all share a common vertex. In this paper, we characterize the local EPT graphs which can be represented in a host tree with maximum degree h.