On BMRN*-colouring of planar digraphs - Archive ouverte HAL
Nothing Special   »   [go: up one dir, main page]

Pré-Publication, Document De Travail Année : 2019
On BMRN*-colouring of planar digraphs
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications (2004 route des Lucioles BP 93 F-06902 Sophia Antipolis (France) - France)
"> COATI - Combinatorics, Optimization and Algorithms for Telecommunications

Résumé

In a recent work, Bensmail, Blanc, Cohen, Havet and Rocha, motivated by applications for TDMA scheduling problems, have introduced the notion of BMRN*-colouring of digraphs, which is a type of arc-colouring with particular colouring constraints. In particular, they gave a special focus to planar digraphs. They notably proved that every planar digraph can be 8-BMRN*-coloured, while there exist planar digraphs for which 7 colours are needed in a BMRN*-colouring. They also proved that the problem of deciding whether a planar digraph can be 3-BMRN*-coloured is NP-hard. In this work, we pursue these investigations on planar digraphs, in particular by answering some of the questions left open by the authors in that seminal work. We exhibit planar digraphs needing 8 colours to be BMRN*-coloured, thus showing that the upper bound of Bensmail, Blanc, Cohen, Havet and Rocha cannot be decreased in general. We also generalize their complexity result by showing that the problem of deciding whether a planar digraph can be k-BMRN*-coloured is NP-hard for every k ∈ {3, ..., 6}. Finally, we investigate the connection between the girth of a planar digraphs and the least number of colours in its BMRN*-colourings.
Fichier principal
Vignette du fichier
bmrn-planar.pdf (525.51 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02195028 , version 1 (26-07-2019)
hal-02195028 , version 2 (08-08-2019)
hal-02195028 , version 3 (02-09-2019)
hal-02195028 , version 4 (30-09-2019)
hal-02195028 , version 5 (25-05-2020)
hal-02195028 , version 6 (15-02-2021)
Identifiants
  • HAL Id : hal-02195028 , version 3

Citer

Julien Bensmail, Foivos Fioravantes. On BMRN*-colouring of planar digraphs. 2019. ⟨hal-02195028v3⟩
676 Consultations
1100 Téléchargements

Partager

More