The kk-edge intersection graphs of paths in a tree

We consider a generalization of edge intersection graphs of paths in a tree. Let PP be a collection of nontrivial simple paths in a tree TT. We define the kk-edge (k⩾1)(k⩾1) intersection graph Γk(P)Γk(P), whose vertices correspond to the members of PP, and two vertices are joined by an edge if the corresponding members of PP share kk edges in TT. An undirected graph GG is called a kk-edge intersection graph of paths in a tree, and denoted by kk-EPT, if G=Γk(P)G=Γk(P) for some PP and TT. It is known that the recognition and the coloring of the 1-EPT graphs are NP-complete. We extend this result and prove that the recognition and the coloring of the kk-EPT graphs are NP-complete for any fixed k⩾1k⩾1. We show that the problem of finding the largest clique on kk-EPT graphs is polynomial, as was the case for 1-EPT graphs, and determine that there are at most O(n3)O(n3) maximal cliques in a kk-EPT graph on nn vertices. We prove that the family of 1-EPT graphs is contained in, but is not equal to, the family of kk-EPT graphs for any fixed k⩾2k⩾2. We also investigate the hierarchical relationships between related classes of graphs, and present an infinite family of graphs that are not kk-EPT graphs for every k⩾2k⩾2. The edge intersection graphs are used in network applications. Scheduling undirected calls in a tree is equivalent to coloring an edge intersection graph of paths in a tree. Also assigning wavelengths to virtual connections in an optical network is equivalent to coloring an edge intersection graph of paths in a tree.