We introduce two variants of proper vertex colourings with imposed
partial ordering on the set of colours. One variant shows close
connections to a fundamental problem in graph theory (directed graph
homomorphism). We study the border between tractability and
intractability for both variants.
We will assume that the vertices of a graph G are integers
from 1 to |V(G)|, and this vertex set will be
considered as a completely ordered set. The set of colours also comes
with a prescribed ordering C=(C,≤), but is only
required to form a partially ordered set. An ordered colouring
of G is a proper vertex colouring with colours
from C satisfying additional requirements.
In the first type of ordered colouring, for every two colours
a,b in C with
a ≤ b we require that every vertex
coloured a is smaller than every vertex
coloured b (according to the complete order of the vertex
set). In the second variant, for every two colours
a,b in C with
a ≤ b, the requirement that a
vertex u coloured a is smaller than a
vertex v coloured b is imposed only
if u and v are adjacent in G.
Our main interest in this talk will be complexity issues: for a fixed
colour poset C=(C,≤), how easy is it to check if a
given graph G allows one of the types of ordered colourings
above.
(This is joint work with Arvind Gupta, Ján Maňuch, Ladislav
Stacho, and Xiaohong Zhao (Simon Fraser University, Canada).)