The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Programme

Logic and Algorithms

Graph partitions

15th March 2006

Author: Pavol Hell (Simon Fraser University)

Abstract

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.