List matrix partitions of special graphs

Let M be a symmetric m x m matrix with entries from the set {0,1,*\}. The M -partition problem asks whether the vertices of a given graph G can be partitioned into m parts V_0,V_1...V_m-1 such that any two distinct vertices in (possibly equal) parts V_i\ and V_j are adjacent if M(i,j)=1, and non-adjacent if M(i,j)=0. This problem generalizes k-coloring and H-coloring problems, as well as many other well-known graph problems. In its list version, which is called the list M -partition problem, a list is assigned to each vertex to restrict its placement into certain parts. An open problem, called the dichotomy problem, asks whether each (list) M -partition problem is polynomial or NP-complete. The difficulty of this problem led to the study of restrictions on the input graphs. A secondary goal was to identify the well-known graph classes for which all (list) M partition problems are polynomial. Several graph classes including perfect graphs, chordal graphs, etc. have been studied so far. In this thesis we continue this line of research, focusing mainly on the list version. We identify certain graph classes defined in terms of geometric configurations, and we prove that for these classes all list M -partition problems are polynomial. These classes include such well-known classes as interval and circular arc graphs. We also consider other standard graphs classes including some generalizations of the aforementioned classes, line graphs and their extensions to quasi-line graphs and claw-free graphs, and some special cases of H-free graphs. For these classes we provide a positive answer to the dichotomy problem for certain kinds of matrices M .