Title of article :
Obstructions to locally injective oriented improper colourings
Author/Authors :
MacGillivray، نويسنده , , Gary and Raspaud، نويسنده , , André and Swarts، نويسنده , , Jacobus، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2014
Pages :
11
From page :
402
To page :
412
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.
Journal title :
European Journal of Combinatorics
Serial Year :
2014
Journal title :
European Journal of Combinatorics
Record number :
1546392
Link To Document :
بازگشت