Geodesic
Acyclic, star, and injective colouring: bounding the diameter
The electronic journal of combinatorics, Tome 29 (2022) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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\leq 2$ but NP-complete if $d\geq 4$, and STAR $3$-COLOURING is polynomial-time solvable if $d\leq 3$ but NP-complete for $d\geq 8.$ As far as we are aware, STAR $3$-COLOURING is the first problem that exhibits a complexity jump for some $d\geq 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.
DOI : 10.37236/10738
Classification : 05C15, 05C78, 05C85, 05C12, 05C45
Mots-clés : acyclic colouring, star colouring, injective colouring, \(L(a, b)\)-labelling 
@article{10_37236_10738,
     author = {Christoph  Brause and Petr Golovach and Barnaby Martin and Pascal Ochem and Dani\"el Paulusma and Siani Smith},
     title = {Acyclic, star, and injective colouring: bounding the diameter},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {2},
     doi = {10.37236/10738},
     zbl = {1491.05074},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10738/}
}
TY  - JOUR
AU  - Christoph  Brause
AU  - Petr Golovach
AU  - Barnaby Martin
AU  - Pascal Ochem
AU  - Daniël Paulusma
AU  - Siani Smith
TI  - Acyclic, star, and injective colouring: bounding the diameter
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10738/
DO  - 10.37236/10738
ID  - 10_37236_10738
ER  - 
%0 Journal Article
%A Christoph  Brause
%A Petr Golovach
%A Barnaby Martin
%A Pascal Ochem
%A Daniël Paulusma
%A Siani Smith
%T Acyclic, star, and injective colouring: bounding the diameter
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/10738/
%R 10.37236/10738
%F 10_37236_10738
Christoph  Brause; Petr Golovach; Barnaby Martin; Pascal Ochem; Daniël Paulusma; Siani Smith. Acyclic, star, and injective colouring: bounding the diameter. The electronic journal of combinatorics, Tome 29 (2022) no. 2. doi: 10.37236/10738

Cité par Sources :