EPT graphs 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: 2014 vol. 42 p. 1 - 8

0103-9059

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertex in common in T. The class of graphs that have an (h,s,t)-representation is denoted by [h,s,t]. It is known that $[infty,2,2]$=EPT, [3,2,2]=EPT Chordal and [4,2,2]= EPT Weakly Chordal.It was an open questionootnote{Equivalences and the complete hierarchy of intersection graphs of paths in a tree, Discrete Applied Mathematics. 156 (2008) 3203-3215.} to know therelationship between the maximum degree h of the host tree and the length n of the longest chordless cycle (n > 3). It is known that if G is in the class [h,2,2], then G has no chordless cycleCn for n > h, since there is a unique EPT representation of Cn as a pie with n slices. The converse is true for h=3, since G must be chordal. The converse is false for h=4, since the complement of the graph C6 has no chordless cycle greater than 4 and the complement of the graph C6 is not in the class [4,2,2]. It was an open question to know if the converse is true for h >4. We prove that the converse is false for h> 4. That is, we find a family F(i,j,k}), with i,j,k>0, such that if i+j+k+2=h, then F(i,j,k) is in the class [h,2,2]-[h-1,2,2] and F(i,j,k) is {Cn, n > h-1}-free.