(Star, k)-colourings of graphs with bounded treewidth - Weffort-Santos, C. A.; Pedrosa, L. L. C. (Anais do Encontro de Teoria da Computação (ETC), 2020)
We study a generalization of graph colouring define as follows. Given a graph G, a (star, k)-colouring of G is a colouring c : V(G) → {1, ..., k} such that every colour class induces a star. We propose an O*(2^(O(tw))k^(tw)-time algorithm that decides whether a graph G of treewidth at most tw admits a (star, k)-colouring. This resolves an open problem posed by Angelini et al. in 2017. Our approach can be extended to other defective colouring models.