Acyclic, Star, and Injective Colouring: Bounding the diameter

Brause, C.; Golovach, P.; Martin, B.; Ochem, P.l; Paulusma, D.; Smith, S.

Abstract

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 ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING. The last problem is also known as L ( 1 , 1 ) -LABELLING and we also consider the framework of L ( a , b ) -LABELLING. We prove a number of (almost-)complete complexity classifications. In particular, we show that for graphs of diameter at most~ d , ACYCLIC 3 -COLOURING is polynomial-time solvable if d ≤ 2 but NP-complete if d ≥ 4 , and STAR 3 -COLOURING is polynomial-time solvable if d ≤ 3 but NP-complete for d ≥ 8. As far as we are aware, STAR 3 -COLOURING is the first problem that exhibits a complexity jump for some d ≥ 3. Our third main result is that L ( 1 , 2 ) -LABELLING is NP-complete for graphs of diameter~ 2 ; we relate the latter problem to a special case of HAMILTONIAN PATH.

Citation

Brause, C., Golovach, P., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2022). Acyclic, Star, and Injective Colouring: Bounding the diameter. Electronic Journal of Combinatorics, 29(2), https://doi.org/10.37236/10738

• Journal Article Type: Article
• Acceptance Date: May 19, 2022
• Online Publication Date: Jun 3, 2022
• Publication Date: 2022
• Deposit Date: Oct 16, 2022
• Publicly Available Date: Oct 17, 2022
• Journal: Electronic Journal of Combinatorics
• Electronic ISSN: 1077-8926
• Publisher: Electronic Journal of Combinatorics
• Peer Reviewed: Peer Reviewed
• Volume: 29
• Issue: 2
• DOI: https://doi.org/10.37236/10738
• Public URL: https://durham-repository.worktribe.com/output/1189097