Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903132 | Discrete Mathematics | 2018 | 19 Pages |
Abstract
One way of defining an oriented colouring of a directed graph Gâ is as a homomorphism from Gâ to a target directed graph Hâ, and an injective oriented colouring of Gâ can be defined as a homomorphism from Gâ to a target directed graph Hâ such that no two in-neighbours of a vertex of Gâ have the same image. Oriented colourings may be constructed using target directed graphs that are nice, as defined by Hell et al. (2001). We extend the work of Hell et al. by considering target graphs that are tournaments, characterizing nice tournaments, and proving that every nice tournament on n vertices is k-nice for some kâ¤n+2. We also give a characterization of tournaments that are nice but not injective-nice.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
T.K. Rapke, K. Seyffarth,