Pavol Hell, Simon Fraser University, Canada
Obstruction Certificates for Geometrically Defined Graph (and Digraph) Classes
In this talk I will focus on obstruction characterizations for interval graphs and their analogues, principally versions of interval bigraphs, interval digraphs, and circular arc-graphs. I will propose a new geometrically defined class of digraphs that generalizes the first three classes, and present an obstruction characterization for it. I will also present a separate obstruction characterization for the class of circular-arc graphs, that gives an answer to a question of Klee, and of Hadwiger and Debrunner, from the early 1960’s. The first three classes are closely related to the complexity of the list homomorphism problem.
This is joint with T. Feder, J. Huang, and A. Rafiey for the interval graphs and their generalizations, and with M. Francis and J. Stacho for the circular arc graphs.