The Complexity of Acyclic, Star and Injective Colouring for H-Free Graphs

Siani A. Smith

Colouring is among the best known problems in computer science. One direction of study has been to consider the complexity of colouring for $H$-free graphs, that is graphs which do not contain $H$ as an induced subgraph. A full dichotomy is known in the case where the number of available colours, $k$, is part of the input whereas infinitely many open cases remain where $k$ is fixed. We study three variants of the colouring problem, acyclic, star and injective colouring. An acyclic colouring of a graph $G$ is a proper colouring in which the union of any two colour classes induces a forest. Similarly a star colouring of $G$ is a proper colouring in which the union of any two colour classes is $P_4$-free, in other words it induces a star forest. Finally, an injective colouring, also known as a distance $2$ colouring or an $L(1,1)$-labelling, is a proper colouring in which the union of any two colour classes is $P_3$-free. In each case we combine new and known results to obtain a full complexity dichotomy where $k$ is fixed and classify all but at most finitely many graphs $H$ where $k$ is part of the input. In fact, for both star and injective colouring, we show that only one open case remains.

This is joint work with Jan Bok, Nikola Jedličková, Barnaby Martin and Daniël Paulusma.

 Overview  Program