A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs

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

MATEMáTICA CONTEMPORâNEA

Sociedad Brasilera de Matemática

Año: 2010 vol. 39 p. 111 - 120

0103-9059

An undirected graph G is called an EPT graph if it is the edge intersection graph of a familiy of paths in a tree. In this paper we define the concept of satellite of a clique and we give a necessary condition to be an EPT graph based on satellites of cliques. We characterize the minimal graphs which do not satisfy the previous condition, as a consequence we present a finite family of minimal forbidden subgraphs for the EPT class.