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.
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact firstname.lastname@example.org.
Member of collection