On local edge intersection graphs of paths on bounded degree trees.

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

MATEMáTICA CONTEMPORâNEA

Sociedad Brasilera de Matemática

Año: 2016 vol. 44 p. 1 - 10

0103-9059

An (h,2,2)-representation of a graph  G is a pair $langle mathcal{P},T angle$ where T is a tree with maximum degree h and $mathcal{P}$ is a family $(P_v)_{vin V(G)}$ of subpaths of T satisfying that two vertices v and v´ of G are adjacent if and only if $P_v$ and $P_{v´}$ have at least two vertices (one edge) in common. We let [h,2,2] denote the class of graphs which admit an (h,2,2)-representation. The well known class of  EPT graphs (also called UE) is the union of the classes [h,2,2] for $hgeq2$. Determining the family of forbidden induced subgraphs for being $EPT$ is an intricate open problem.Our aim is to characterize by forbidden induced subgraphs  the class [h,2,2] for a fixed h. For this purpose, we search minimal structures in an EPT graph, that cannot be represented using a host tree with maximum degree h.We define recursively the following family of graphs  we have called gates:(i) A chordless cycle $C_n$  is a gate for every  $ngeq 4$; (ii) If G is a gate,  C and C´ are disjoint cliques (maximal complete subgraphs) of G, and $P : v_1,...,v_k$ is a chordless path disjoint from G with $kgeq 2$, then the  union of G and Pplus all  edges between $v_1$ and the vertices of  C, and all edges between  $v_k$ and the vertices of  C´ is a gate;(iii) There are no more gates.If the number of cliques of a gate G is h then we say that G is an h-gate. In this work, we show that h-gates are EPT graphs that cannot be represented in a host tree with maximum degree less than h, this generalizes one of our previous results ootnote{EPT graphs on bounded degree trees, accepted for publication in Matem´atica Contempor´anea}. Even more, we conjecture that an EPT graph belongs to [h,2,2] if and only if it has no induced subgraph isomorphic to a k-gate for k>h.We also prove that the conjecture is true in a subclass of local-EPT graphs, this is the EPT graphs that admit a representation in which all paths of $mathcal{P}$ share a vertex of T.