Obstructions to Injective Oriented Colourings

详细信息    查看全文

• 作者：Gary  ; MacGillivray^a ;   ; ¹ ;   ; ^{gmacgill@math.uvic.ca} ; André ;   ; Raspaud^b ;   ; ^{raspaud@labri.fr} ; Jacobus  ; Swarts^c ;   ; ^{Jacobus.Swarts@viu.ca}
• 关键词：oriented colouring ; injective colouring ; homomorphism ; colouring extension ; colour critical
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2011
• 出版时间：1 December 2011
• 年：2011
• 卷：38
• 期：Complete
• 页码：597-605
• 全文大小：235 K

文摘

The question of deciding the existence of an oriented colouring which must also be locally injective on the in-neighbourhood of each vertex is polynomially solvable when the number of colours is at most three. In these cases, we describe efficient algorithms, based on colouring extension, which produce either the desired colouring or a forbidden substructure.