Geodesic
Oriented Incidence Colourings of Digraphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 191-210

Voir la notice de l'article provenant de la source Library of Science

Brualdi and Quinn Massey [6] defined incidence colouring while studying the strong edge chromatic index of bipartite graphs. Here we introduce a similar concept for digraphs and define the oriented incidence chromatic number. Using digraph homomorphisms, we show that the oriented incidence chromatic number of a digraph is closely related to the chromatic number of the underlying simple graph. This motivates our study of the oriented incidence chromatic number of symmetric complete digraphs. We give upper and lower bounds for the oriented incidence chromatic number of these graphs, as well as digraphs arising from common graph constructions and decompositions. Additionally we construct, for all k gt; 2, a target digraph Hk for which oriented incidence k colouring is equivalent to homomorphism to Hk.
Keywords: digraph homomorpism, graph colouring, incidence colouring, computational complexity 
@article{DMGT_2019_39_1_a15,
     author = {Duffy, Christopher and MacGillivray, Gary and Ochem, Pascal and Raspaud, Andr\'e},
     title = {Oriented {Incidence} {Colourings} of {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {191--210},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a15/}
}
TY  - JOUR
AU  - Duffy, Christopher
AU  - MacGillivray, Gary
AU  - Ochem, Pascal
AU  - Raspaud, André
TI  - Oriented Incidence Colourings of Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 191
EP  - 210
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a15/
LA  - en
ID  - DMGT_2019_39_1_a15
ER  - 
%0 Journal Article
%A Duffy, Christopher
%A MacGillivray, Gary
%A Ochem, Pascal
%A Raspaud, André
%T Oriented Incidence Colourings of Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 191-210
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a15/
%G en
%F DMGT_2019_39_1_a15
Duffy, Christopher; MacGillivray, Gary; Ochem, Pascal; Raspaud, André. Oriented Incidence Colourings of Digraphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 191-210. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a15/