Acyclic, Star, and Injective Colouring: Bounding the Diameter
Acyclic, Star, and Injective Colouring: Bounding the Diameter
We examine the effect of bounding the diameter for a number of natural and well-studied 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 …