Geodesic
A Study of $k$-dipath Colourings of Oriented Graphs
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1

Voir la notice de l'article provenant de la source Episciences

We examine $t$-colourings of oriented graphs in which, for a fixed integer $k \geq 1$, vertices joined by a directed path of length at most $k$ must be assigned different colours. A homomorphism model that extends the ideas of Sherk for the case $k=2$ is described. Dichotomy theorems for the complexity of the problem of deciding, for fixed $k$ and $t$, whether there exists such a $t$-colouring are proved. 
@article{DMTCS_2018_20_1_a6,
     author = {Duffy, Christopher and MacGillivray, Gary and Sopena, \'Eric},
     title = {A {Study} of $k$-dipath {Colourings} of {Oriented} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-6},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-6/}
}
TY  - JOUR
AU  - Duffy, Christopher
AU  - MacGillivray, Gary
AU  - Sopena, Éric
TI  - A Study of $k$-dipath Colourings of Oriented Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-6/
DO  - 10.23638/DMTCS-20-1-6
LA  - en
ID  - DMTCS_2018_20_1_a6
ER  - 
%0 Journal Article
%A Duffy, Christopher
%A MacGillivray, Gary
%A Sopena, Éric
%T A Study of $k$-dipath Colourings of Oriented Graphs
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-6/
%R 10.23638/DMTCS-20-1-6
%G en
%F DMTCS_2018_20_1_a6
Duffy, Christopher; MacGillivray, Gary; Sopena, Éric. A Study of $k$-dipath Colourings of Oriented Graphs. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi: 10.23638/DMTCS-20-1-6

Cité par Sources :