Skip to content

LAA

Seminar

Graph partitions

Hell, P (Simon Fraser)
Wednesday 15 March 2006, 11:00-12:00

Seminar Room 1, Newton Institute

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.

Presentation

[ppt ]

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧