Representations of Edge Intersection Graphs of Paths in a Tree

Abstract : Let $\mathcal{P}$ be a collection of nontrivial simple paths in a tree $T$. The edge intersection graph of $\mathcal{P}$, denoted by EPT($\mathcal{P}$), has vertex set that corresponds to the members of $\mathcal{P}$, and two vertices are joined by an edge if the corresponding members of $\mathcal{P}$ share a common edge in $T$. An undirected graph $G$ is called an edge intersection graph of paths in a tree, if $G = EPT(\mathcal{P})$ for some $\mathcal{P}$ and $T$. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph. It is known that recognition and coloring of EPT graphs are NP-complete problems. However, the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs, and therefore can be colored in polynomial time complexity. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. This also implies that the coloring of the edge intersection graph of paths in a degree 4 tree is polynomial. We raise a number of intriguing conjectures regarding related families of graphs.
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.87-92, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184396
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:39:36
Dernière modification le : jeudi 11 mai 2017 - 01:02:51
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:07:01

Fichier

dmAE0118.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184396, version 1

Collections

Citation

Martin Charles Golumbic, Marina Lipshteyn, Michal Stern. Representations of Edge Intersection Graphs of Paths in a Tree. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.87-92, 2005, DMTCS Proceedings. 〈hal-01184396〉

Partager

Métriques

Consultations de la notice

116

Téléchargements de fichiers

123