Representing edge intersection graphs of paths on degree 4 trees Original Research Article

Let image be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of image, denoted by image, has vertex set that corresponds to the members of image, and two vertices are joined by an edge if and only if the corresponding members of image share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if image for some image and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph. An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement image possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs.