Discussiones Mathematicae Graph Theory | |
Oriented Incidence Colourings of Digraphs | |
Duffy Christopher1  MacGillivray Gary2  Ochem Pascal3  Raspaud André4  | |
[1] Department of Mathematics and Statistics University of SaskatchewanSaskatoon, Canada;Department of Mathematics and Statistics University of VictoriaVictoria, Canada;LIRMM, CNRS, Université de Montpellier,Montpellier, France;LaBRI UMR CNRS 5800 Université Bordeaux 1,Bordeaux, France; | |
关键词: digraph homomorpism; graph colouring; incidence colouring; computational complexity; 05c15; | |
DOI : 10.7151/dmgt.2076 | |
来源: DOAJ |
【 摘 要 】
Brualdi and Quinn Massey [6] defined incidence colouring while study- ing 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 inci- dence 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 > 2, a target digraph Hkfor which oriented incidence k colouring is equivalent to homomorphism to Hk.
【 授权许可】
Unknown