Article ID Journal Published Year Pages File Type
6424236 European Journal of Combinatorics 2014 11 Pages PDF
Abstract

Oriented colourings that are injective on in-neighbourhoods, but which need not be proper colourings, are considered. We first find some bounds on the number of colours needed, and determine the complexity of the associated decision problem. We then consider the polynomial cases, and describe efficient algorithms, based on colouring extensions, which produce either a colouring with the given number of colours or a forbidden substructure.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,