Matrix partitions of digraphs

The matrix partition problem has been of recent interest in graph theory. Matrix partitions generalize the study of graph colourings and homomorphisms. Many well-known graph partition problems can be stated in terms of matrices. For example skew partitions, split partitions, homogeneous sets, clique-cutsets, stable-cutsets and k-colourings can all be modeled as matrix partitions. For each matrix partition problem there is an equivalent trigraph H-colouring problem. We show a ‘dichotomy’ for the class of list H-colouring problems where H is a so-called trigraph path. For each trigraph path H we show that the list H-colouring problem is either NP-complete or polynomial time solvable. For each trigraph path H we associate a digraph H– such that the list H-colouring problem is polynomial time solvable if the list H-colouring problem is polynomial time solvable, and is NP-complete otherwise.