Representing edge intersection graphs of paths on degree 4 trees

摘要

Let be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of , denoted by , has vertex set that corresponds to the members of , and two vertices are joined by an edge if and only if the corresponding members of share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if for some 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.