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/

[1] K. Appel, W. Haken and J. Koch, Every planar map is four colorable. Part rm II: Reducibility, Illinois J. Math. 21 (1977) 491-567.

[2] J. Bang-Jensen, P. Hell and G. MacGillivray, The complexity of colouring by semi-complete digraphs, SIAM J. Discrete Math. 1 (1988) 281-298. doi: 10.1137/0401029

[3] L. Barto, M. Kozik and T. Niven, The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell), SIAM J. Comput. 38 (2009) 1782-1802. doi: 10.1137/070708093

[4] J. Bensmail, C. Duffy and S. Sen, Analogues of cliques for (m, n)-colored mixed graphs, Graphs Combin. 33 (2017) 735 - 750. doi: 10.1007/s00373-017-1807-2

[5] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, London, 2008).

[6] R.A. Brualdi and J.J. Quinn Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58. doi: 10.1016/0012-365X(93)90286-3

[7] B. Courcelle, The monadic second order logic of graphs VI: on several representa- tions of graphs by relational structures., Discrete Appl. Math. 54 (1994) 117-129. doi: 10.1016/0166-218X(94)90019-1

[8] W.D. Fellner, On minimal graphs, Theoret. Comput. Sci. 17 (1982) 103-110. doi: 10.1016/0304-3975(82)90135-9

[9] R.L. Graham and N.J.A. Sloane, Lower bounds for constant weight codes, IEEE Trans. Inform. Theory 26 (1980) 37-43. doi: 10.1109/TIT.1980.1056141

[10] P. Hell and J. Nešetřil, On the complexity of H-coloring, J. Combin. Theory Ser. B 48 (1990) 92-110. doi: 10.1016/0095-8956(90)90132-J

[11] M. Hosseini Dolama, E. Sopena and X. Zhu, Incidence coloring of k-degenerated graphs, Discrete Math. 283 (2004) 121-128. doi: 10.1016/j.disc.2004.01.015

[12] W. Klostermeyer and G. MacGillivray, Homomorphisms and oriented colorings of equivalence classes of oriented graphs, Discrete Math. 274 (2004) 161-172. doi: 10.1016/S0012-365X(03)00086-4

[13] A.V. Kostochka, E. Sopena and X. Zhu, Acyclic and oriented chromatic numbers of graphs, J. Graph Theory 24 (1997) 331-340. doi: 10.1002/(SICI)1097-0118(199704)24:4h331::AID-JGT5i3.0.CO;2-P

[14] G. MacGillivray and K. Sherk, A theory of 2-dipath colourings, Australas. J. Com- bin. 60 (2014) 11-26.

[15] G. MacGillivray and J.S. Swarts, Obstructions to homomorphisms involving the graft extension, manuscript.

[16] T.H. Marshall, Homomorphism bounds for oriented planar graphs, J. Graph Theory 55 (2007) 175-190. doi: 10.1002/jgt.20233

[17] J. Nešetřil and A. Pultr, On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978) 287-300. doi: 10.1016/0012-365X(78)90062-6

[18] S. Sen, Maximum order of a planar oclique is 15, in: Proc. 23rd International Workshop on Combinatorial Algorithms, W.F. Smyth and S. Arumugam (Ed(s)), (Springer, 2012) 130-142. doi: 10.1007/978-3-642-35926-2 16

[19] E. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369. doi: 10.1016/S0012-365X(00)00216-8

[20] P.K. Sun, Incidence coloring of regular graphs and complement graphs, Taiwanese J. Math. 16 (2012) 2289-2295. doi: 10.11650/twjm/1500406852

[21] E. Welzl, Color-families are dense, Theoret. Comput. Sci. 17 (1982) 29-41. doi: 10.1016/0304-3975(82)90129-3

[22] J. Wu, Some results on the incidence coloring number of a graph, Discrete Math. 309 (2009) 3866-3870. doi: 10.1016/j.disc.2008.10.027

[23] K. Young, 2-Dipath and Proper 2-Dipath Colouring (Masters Thesis, University of Victoria, 2009).