Oriented Incidence Colourings of Digraphs

Discussiones Mathematicae Graph Theory

Duffy Christopher¹  MacGillivray Gary²  Ochem Pascal³  Raspaud André⁴ 

[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