dc.contributor.author | Brause, Christoph | |
dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Martin, Barnaby | |
dc.contributor.author | Ochem, Pascal | |
dc.contributor.author | Paulusma, Daniël | |
dc.contributor.author | Smith, Siani | |
dc.date.accessioned | 2023-03-20T12:21:02Z | |
dc.date.available | 2023-03-20T12:21:02Z | |
dc.date.created | 2022-09-13T08:36:18Z | |
dc.date.issued | 2022 | |
dc.identifier.issn | 1097-1440 | |
dc.identifier.uri | https://hdl.handle.net/11250/3059247 | |
dc.description.abstract | We examine the effect of bounding the diameter for a number of natural and well-studied variants of the COLOURING problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING. The last problem is also known as $L(1,1)$-LABELLING and we also consider the framework of $L(a,b)$-LABELLING. We prove a number of (almost-)complete complexity classifications. In particular, we show that for graphs of diameter at most~$d$, ACYCLIC $3$-COLOURING is polynomial-time solvable if $d\leq 2$ but NP-complete if $d\geq 4$, and STAR $3$-COLOURING is polynomial-time solvable if $d\leq 3$ but NP-complete for $d\geq 8.$ As far as we are aware, STAR $3$-COLOURING is the first problem that exhibits a complexity jump for some $d\geq 3.$ Our third main result is that $L(1,2)$-LABELLING is NP-complete for graphs of diameter~$2$; we relate the latter problem to a special case of HAMILTONIAN PATH. | en_US |
dc.language.iso | eng | en_US |
dc.rights | Attribution-NoDerivatives 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nd/4.0/deed.no | * |
dc.title | Acyclic, star, and injective colouring: bounding the diameter∗ | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2022 The Author(s) | en_US |
dc.source.articlenumber | P2.43 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.37236/10738 | |
dc.identifier.cristin | 2051034 | |
dc.source.journal | The Electronic Journal of Combinatorics | en_US |
dc.identifier.citation | The Electronic Journal of Combinatorics. 2022, 29 (2), P2.43. | en_US |
dc.source.volume | 29 | en_US |
dc.source.issue | 2 | en_US |