Ordered colourings of graphs

Jan van den Heuvel
London School of Economics


Abstract:

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).)

Retour au séminaire