Obstructions to Trigraph Homomorphisms
Wing Xie · Summit (Simon Fraser University) · 2006
Many graph partition problems seek a partition into parts with certain internal constraints on each part, and similar external constraints between the parts.Such problems have been traditionally modeled using matrices, as the so-called M-partition problems.More recently, they have also been modeled as trigraph homomorphism problems.This thesis consists of two parts.In the first part, we survey the literature dealing with both general and restricted versions of these problems.Most existing results attempt to classify these problems as NPcomplete or polynomial time solvable.In the second part of the thesis, we investigate which of these problems can be characterized by a finite set of forbidden induced subgraphs.We develop new tools and use them to find all such partition problems with up to five parts.We also observe that these problems are automatically polynomial time solvable.