Acyclic, star, and injective colouring: bounding the diameter (Q5918693)

From MaRDI portal
scientific article; zbMATH DE number 7541148
Language Label Description Also known as
English
Acyclic, star, and injective colouring: bounding the diameter
scientific article; zbMATH DE number 7541148

    Statements

    Acyclic, star, and injective colouring: bounding the diameter (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    13 June 2022
    0 references
    Summary: 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\leqslant 2\) but NP-complete if \(d\geqslant 4\), and Star \(3\)-Colouring is polynomial-time solvable if \(d\leqslant 3\) but NP-complete for \(d\geqslant 8\). As far as we are aware, Star \(3\)-Colouring is the first problem that exhibits a complexity jump for some \(d\geqslant 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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    acyclic colouring
    0 references
    star colouring
    0 references
    injective colouring
    0 references
    \(L(a, b)\)-labelling
    0 references
    0 references
    0 references
    0 references
    0 references