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.
Abstract
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 (294Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://www.springer.com/gp/computer-science/lncs/ |
| 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
| Export: | |
| Look up in GoogleScholar |
