We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Acyclic, star and injective colouring: bounding the diameter

Brause, C. and Golovach, P. A. and Martin, B. and Paulusma, D. and Smith, S. (2021) 'Acyclic, star and injective colouring: bounding the diameter.', WG 2021 Virtual, 23-25 June 2021.


We examine the effect of bounding the diameter for wellstudied 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, for Acyclic 3-Colouring, Star 3-Colouring and L(1, 2)-Labelling

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:28 April 2021
Date deposited:24 August 2021
Date of first online publication:2021
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar