Article ID Journal Published Year Pages File Type
8903132 Discrete Mathematics 2018 19 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,