Siani Smith

Bristol / HIMR

Acyclic, Star and Injective Colouring: Complexity for H-free Graphs

Combinatorics Seminar

2nd November 2022, 11:00 am – 12:00 pm
Fry Building, G.07

We study the computational complexity of three variants of the colouring problem, acyclic, star and injective colouring. Almost complete complexity dichotomies are obtained for each problem, both in the case where the number of colours is fixed and where it is part of the input. This is joint work with Jan Bok, Nikola Jedlickova, Barnaby Martin, Pascal Ochem and Daniel Paulusma.

Comments are closed.