EPT graphs: Relationship between the maximum degree h of the host tree and the length n of the longest chordless cycle.

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

Buenos Aires

Seminario; Sexto Seminario de la Red Latinoamericana de Optimización Discreta y grafos: Teoría, Algoritmos y Aplicaciones.; 2013

Instituto de Cálculo de la Universidad Nacional de Buenos Aires

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 $cap$ chordal and [4,2,2]= EPT $cap$ weakly chordal.It was an open question ootnote{Equivalences and the complete hierarchy of intersection graphs of paths in a tree, Discrete Applied Mathematics. 156 (2008) 3203-3215.} to know the relationship between the maximum degree h of the host tree and the length n of the longest chordless cycle ($ngeq 4$). It is known that if $Gin [h,2,2]$, then G has no chordless cycle $C_n$ for $ngeq h+1$, since there is a unique EPT representation of $C_n$ 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 graph $ar{C}_6$ has no chordless cycle greater than 4 and $ar{C}_6 otin [4,2,2]$. It was an open question to know if the converse is true for $hgeq 5$. We prove that the converse is false for $hgeq 5$. That is, we find a family $F_{i,j,k}$, with $i,j,kgeq 1$, such that if i+j+k+2=h, then $F_{i,j,k}in [h,2,2]-[h-1,2,2]$ and $F_{i,j,k}$ is ${C_{n}, ngeq h}$-free.