Acyclic, Star, and Injective Colouring: Bounding the Diameter - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles The Electronic Journal of Combinatorics Year : 2022

Acyclic, Star, and Injective Colouring: Bounding the Diameter

Christoph Brause
  • Function : Author
  • PersonId : 1261356
Petr Golovach
Barnaby Martin
Pascal Ochem
Daniël Paulusma
Siani Smith


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.
Fichier principal
Vignette du fichier
10738-PDF file-40547-2-10-20220527.pdf (842.95 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Licence : CC BY ND - Attribution - NoDerivatives

Dates and versions

lirmm-03799962 , version 1 (09-06-2023)


Attribution - NoDerivatives



Christoph Brause, Petr Golovach, Barnaby Martin, Pascal Ochem, Daniël Paulusma, et al.. Acyclic, Star, and Injective Colouring: Bounding the Diameter. The Electronic Journal of Combinatorics, 2022, 29 (2), pp.#P2.43. ⟨10.37236/10738⟩. ⟨lirmm-03799962⟩
24 View
3 Download



Gmail Facebook Twitter LinkedIn More