Injective Oriented Colourings

详细信息    查看全文

• 作者：Gary MacGillivray ; Andr¨¦ Raspaud ; Jacobus Swarts
• 关键词：oriented colouring ; injective colouring ; digraph ; homomorphisms
• 刊名：Lecture Notes in Computer Science
• 出版年：2010
• 出版时间：2010
• 年：2010
• 卷：5911
• 期：1
• 页码：262-272
• 全文大小：187.8 KB

文摘

We develop the theory of oriented colourings which are injective on in-neighbourhoods. The complexity of deciding if the minimum number of colours is at most the fixed integer k is determined, as is Brooks-Theorem type bound. The latter relies, in part, on a characterization of the oriented graphs in which each vertex must be assigned a different colour. A better, tight bound is determined for oriented trees, and a linear algorithm that decides if a given tree can be coloured with at most k colours, where k is fixed, is described.