On superperfection of edge-intersection graphs of paths

Abstract : The Routing and Spectrum Assignment problem in Flexgrid Elastic Optical Networks can be modeled in two phases: a selection of paths in the network and an interval coloring problem in the edge-intersection graph of these paths. The interval chromatic number equals the smallest size of a spectrum such that a proper interval coloring is possible, the weighted clique number is a natural lower bound. Graphs where both parameters coincide for all induced subgraphs and for all possible integral weights are called superperfect. We examine the question which minimal non-superperfect graphs can occur in the edge-intersection graphs of paths in different underlying networks and show that for any possible network (even if it is restricted to a path) the resulting edge-intersection graphs are not necessarily superperfect.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.uca.fr/hal-02017433
Contributor : Annegret Wagler <>
Submitted on : Friday, April 26, 2019 - 11:16:06 AM
Last modification on : Friday, May 3, 2019 - 1:21:54 AM

File

KW_SuperEIGoP_HAL_v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02017433, version 2

Citation

Hervé Kerivin, Annegret K. Wagler. On superperfection of edge-intersection graphs of paths. 2019. ⟨hal-02017433v2⟩

Share

Metrics

Record views

55

Files downloads

42