{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:30Z","timestamp":1753889790809,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Graph Theory","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p xml:lang=\"en\">We investigate graph colouring models for the purpose of optimizing TDMA link scheduling in Wireless Networks. Inspired by the BPRN-colouring model recently introduced by Rocha and Sasaki, we introduce a new colouring model, namely the BMRN-colouring model, which can be used to model link scheduling problems where particular types of collisions must be avoided during the node transmissions. In this paper, we initiate the study of the BMRN-colouring model by providing several bounds on the minimum number of colours needed to BMRN-colour digraphs, as well as several complexity results establishing the hardness of finding optimal colourings. We also give a special focus on these considerations for planar digraph topologies, for which we provide refined results.<\/jats:p>","DOI":"10.23638\/dmtcs-21-3-24","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:55:38Z","timestamp":1743699338000},"source":"Crossref","is-referenced-by-count":0,"title":["Backbone colouring and algorithms for TDMA scheduling"],"prefix":"10.23638","volume":"Vol. 21 no. 3","author":[{"given":"Julien","family":"Bensmail","sequence":"first","affiliation":[{"name":"Combinatorics, Optimization and Algorithms for Telecommunications"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thibaut","family":"Blanc","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03rxtdc22","id-type":"ROR","asserted-by":"publisher"}],"name":"\u00c9cole normale sup\u00e9rieure - Rennes","acronym":["ENS Rennes"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3341-3712","authenticated-orcid":false,"given":"Nathann","family":"Cohen","sequence":"additional","affiliation":[{"name":"Graphes, Algorithmes et Combinatoire (LRI)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3447-8112","authenticated-orcid":false,"given":"Fr\u00e9d\u00e9ric","family":"Havet","sequence":"additional","affiliation":[{"name":"Combinatorics, Optimization and Algorithms for Telecommunications"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2608-1844","authenticated-orcid":false,"given":"Leonardo","family":"Rocha","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00sec1m50","id-type":"ROR","asserted-by":"publisher"}],"name":"Universidade Estadual do Cear\u00e1"},{"id":[{"id":"https:\/\/ror.org\/00sec1m50","id-type":"ROR","asserted-by":"publisher"}],"name":"Universidade Estadual do Cear\u00e1 [Brasil] = State University of Cear\u00e1 [Brazil]","acronym":["UECE"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2019,7,13]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/hal.science\/hal-01851600v4\/document","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/hal.science\/hal-01851600v4\/document","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:55:38Z","timestamp":1743699338000},"score":1,"resource":{"primary":{"URL":"http:\/\/dmtcs.episciences.org\/5079"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,13]]},"references-count":0,"journal-issue":{"issue":"Graph Theory","published-online":{"date-parts":[[2019,7,13]]}},"URL":"https:\/\/doi.org\/10.23638\/dmtcs-21-3-24","relation":{"has-preprint":[{"id-type":"uri","id":"https:\/\/hal.science\/hal-01851600v3","asserted-by":"subject"},{"id-type":"uri","id":"https:\/\/hal.science\/hal-01851600v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"uri","id":"https:\/\/hal.science\/hal-01851600v4","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"type":"electronic","value":"1365-8050"}],"subject":[],"published":{"date-parts":[[2019,7,13]]},"article-number":"5079"}}