Seminar Room 1, Newton Institute
I will discuss vertex partitions V1, V2,..., Vk, where each Vi is a clique, a stable set, or an arbitrary set, and each pair Vi, Vj is completely adjacent, completely nonadjacent, or arbitrary. Many common partitions in the study of perfect graphs have such structure. The main goal is to decide when the existence of such a partition can be characterized by a finite set of forbidden induced subgraphs. These partitions can be viewed as restricted constraint satisfaction problems; connections to the dichotomy conjecture will also be discussed.