{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:09:43Z","timestamp":1760400583044,"version":"build-2065373602"},"reference-count":33,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T00:00:00Z","timestamp":1757030400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>ABSTRACT<\/jats:title><jats:p>Brooks' Theorem is a fundamental result on graph colouring, stating that the chromatic number of a graph is almost always upper bounded by its maximal degree. Lov\u00e1sz showed that such a colouring may then be computed in linear time when it exists. Many analogues are known for variants of (di)graph colouring, notably for list\u2010colouring and partitions into subgraphs with prescribed degeneracy. One of the most general results of this kind is due to Borodin, Kostochka, and Toft, when asking for classes of colours to satisfy \u2018variable degeneracy\u2019 constraints. An extension of this result to digraphs has recently been proposed by Bang\u2010Jensen, Schweser, and Stiebitz, by considering colourings as partitions into \u2018variable weakly degenerate\u2019 subdigraphs. Unlike earlier variants, there exists no linear\u2010time algorithm to produce colourings for these generalisations. We introduce the notion of <jats:italic>(variable) bidegeneracy<\/jats:italic> for digraphs, capturing multiple (di)graph degeneracy variants. We define the corresponding concept of \u2010dicolouring, where  is a vector of functions, and an \u2010dicolouring requires vertices coloured  to induce a \u2018strictly\u2010\u2010bidegenerate\u2019 subdigraph. We prove an analogue of Brooks' theorem for \u2010dicolouring, generalising the result of Bang\u2010Jensen et al., and earlier analogues in turn. Our new approach provides a linear\u2010time algorithm that, given a digraph , either produces an \u2010dicolouring of , or correctly certifies that none exist. This yields the first linear\u2010time algorithms to compute (di)colourings corresponding to the aforementioned generalisations of Brooks' theorem. In turn, it gives an unified framework to compute such colourings for various intermediate generalisations of Brooks' theorem such as list\u2010(di)colouring and partitioning into (variable) degenerate sub(di)graphs.<\/jats:p>","DOI":"10.1002\/jgt.23266","type":"journal-article","created":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T10:55:12Z","timestamp":1757069712000},"page":"496-513","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Brooks\u2010Type Colourings of Digraphs in Linear Time"],"prefix":"10.1002","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3228-9622","authenticated-orcid":false,"given":"Daniel","family":"Gon\u00e7alves","sequence":"first","affiliation":[{"name":"LIRMM Universit\u00e9 de Montpellier, CNRS Montpellier France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lucas","family":"Picasarri\u2010Arrieta","sequence":"additional","affiliation":[{"name":"National Institute of Informatics Tokyo Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8108-4036","authenticated-orcid":false,"given":"Amadeus","family":"Reinald","sequence":"additional","affiliation":[{"name":"LIRMM Universit\u00e9 de Montpellier, CNRS Montpellier France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2025,9,5]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90089-1"},{"key":"e_1_2_7_4_1","unstructured":"B.BaetzandD. R.Wood \u201cBrooks' Vertex\u2010Colouring Theorem in Linear Time \u201darXiv preprint arXiv:1401.8023(2014)."},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.12.007"},{"key":"e_1_2_7_6_1","doi-asserted-by":"crossref","unstructured":"S.Assadi Y.Chen andS.Khanna \u201cSublinear Algorithms for (\u0394+1) Vertex Coloring \u201d inProceedings of the Thirtieth Annual ACM\u2010SIAM Symposium on Discrete Algorithms(Society for Industrial and Applied Mathematics 2019) 767\u2013786.","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-50065-7"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22109"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.37236\/6043"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.4310\/JOC.2022.v13.n1.a1"},{"key":"e_1_2_7_11_1","unstructured":"P.Aboulker G.Aubian andP.Charbit \u201cDigraph Colouring and Arc\u2010Connectivity \u201darXiv preprint arXiv:2304.04690(2023)."},{"issue":"3","key":"e_1_2_7_12_1","first-page":"2","article-title":"Vertex Colorings With Given Colors","volume":"29","author":"Vizing V. G.","year":"1976","journal-title":"Diskretnyi Analiz"},{"key":"e_1_2_7_13_1","unstructured":"O. V.Borodin \u201cProblems of Colouring and of Covering the Vertex Set of a Graph by Induced Subgraphs\u201d (PhD thesis Novosibirsk State University 1979)."},{"issue":"4","key":"e_1_2_7_14_1","first-page":"125","article-title":"Choosability in Graphs","volume":"26","author":"Erd\u0151s P.","year":"1979","journal-title":"Congressus Numerantium"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/11.2.113"},{"key":"e_1_2_7_16_1","first-page":"3","article-title":"On Decomposition of Graphs Into Degenerate Subgraphs","volume":"28","author":"Borodin O. V.","year":"1976","journal-title":"Diskretnyi Analiz"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2023.103771"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00221-6"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22575"},{"key":"e_1_2_7_20_1","doi-asserted-by":"publisher","DOI":"10.5614\/ejgta.2021.9.1.1"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.113186"},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(82)90046-6"},{"key":"e_1_2_7_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2009.05.027"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.113193"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.23066"},{"key":"e_1_2_7_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/100803870"},{"key":"e_1_2_7_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1386827"},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20003"},{"key":"e_1_2_7_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2023.103876"},{"key":"e_1_2_7_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649987"},{"key":"e_1_2_7_31_1","unstructured":"M. R.GareyandD. S.Johnson Computers and Intractability(Freeman San Francisco 1979)."},{"key":"e_1_2_7_32_1","doi-asserted-by":"crossref","unstructured":"J.Bang\u2010JensenandG. Z.Gutin Digraphs: Theory Algorithms and Applications(Springer\u2010Verlag London 2009).","DOI":"10.1007\/978-1-84800-998-1"},{"key":"e_1_2_7_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_7_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.01.016"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.23266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T05:14:08Z","timestamp":1760332448000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.23266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,5]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1002\/jgt.23266"],"URL":"https:\/\/doi.org\/10.1002\/jgt.23266","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"type":"print","value":"0364-9024"},{"type":"electronic","value":"1097-0118"}],"subject":[],"published":{"date-parts":[[2025,9,5]]},"assertion":[{"value":"2024-06-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}