Matrix partitions of digraphs
David G. Schell · Summit (Simon Fraser University) · 2008
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.