Matrix partitions of digraphs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2008
Authors/Contributors
Abstract
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.
Document
Copyright statement
Copyright is held by the author.
Permissions
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 summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Attachment Size
etd3600.pdf 617.51 KB