Abstract
A kcolouring c of a graph G is a mapping V(G) → {1,2,… k} such that c(u) ≠ c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. 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. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as L(1,1)Labelling).
A classical complexity result on Colouring is a wellknown dichotomy for Hfree graphs, which was established twenty years ago (in this context, a graph is Hfree if and only if it does not contain H as an induced subgraph). Moreover, this result has led to a large collection of results, which helped us to better understand the complexity of Colouring. In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years.
We initiate such a systematic complexity study, and similar to the study of Colouring we use the class of Hfree graphs as a testbed. We prove the following results:
1) We give almost complete classifications for the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring for Hfree graphs.
2) If the number of colours k is fixed, that is, not part of the input, we give full complexity classifications for each of the three problems for Hfree graphs. From our study we conclude that for fixed k the three problems behave in the same way, but this is no longer true if k is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs.
BibTeX  Entry
@InProceedings{bok_et_al:LIPIcs:2020:12888,
author = {Jan Bok and Nikola Jedlic̆kov{\'a} and Barnaby Martin and Dani{\"e}l Paulusma and Siani Smith},
title = {{Acyclic, Star and Injective Colouring: A Complexity Picture for HFree Graphs}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {22:122:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12888},
URN = {urn:nbn:de:0030drops128885},
doi = {10.4230/LIPIcs.ESA.2020.22},
annote = {Keywords: acyclic colouring, star colouring, injective colouring, Hfree, dichotomy}
}
Keywords: 

acyclic colouring, star colouring, injective colouring, Hfree, dichotomy 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 