On BMRN*-colouring of planar digraphs
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 dig...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-02-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5798/pdf |
| _version_ | 1797269983322963968 |
|---|---|
| author | Julien Bensmail Foivos Fioravantes |
| author_facet | Julien Bensmail Foivos Fioravantes |
| author_sort | Julien Bensmail |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:02Z |
| format | Article |
| id | doaj.art-0cba365fe0f9497f8ae8001936d13598 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:02Z |
| publishDate | 2021-02-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-0cba365fe0f9497f8ae8001936d135982024-03-07T15:44:09ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-02-01vol. 23 no. 1Graph Theory10.46298/dmtcs.57985798On BMRN*-colouring of planar digraphsJulien Bensmail0Foivos Fioravantes1https://orcid.org/0000-0001-8217-030XCombinatorics, Optimization and Algorithms for TelecommunicationsCombinatorics, Optimization and Algorithms for TelecommunicationsIn 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.https://dmtcs.episciences.org/5798/pdfbmrn*-colouringplanar digraphstdma scheduling[info.info-dm]computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Julien Bensmail Foivos Fioravantes On BMRN*-colouring of planar digraphs Discrete Mathematics & Theoretical Computer Science bmrn*-colouring planar digraphs tdma scheduling [info.info-dm]computer science [cs]/discrete mathematics [cs.dm] |
| title | On BMRN*-colouring of planar digraphs |
| title_full | On BMRN*-colouring of planar digraphs |
| title_fullStr | On BMRN*-colouring of planar digraphs |
| title_full_unstemmed | On BMRN*-colouring of planar digraphs |
| title_short | On BMRN*-colouring of planar digraphs |
| title_sort | on bmrn colouring of planar digraphs |
| topic | bmrn*-colouring planar digraphs tdma scheduling [info.info-dm]computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/5798/pdf |
| work_keys_str_mv | AT julienbensmail onbmrncolouringofplanardigraphs AT foivosfioravantes onbmrncolouringofplanardigraphs |