Tutte Colloquium - Nicolas Trotignon

Title: Widths in even-hole-free graphs

Abstract:

Historically, the study of even-hole-free graphs is motivated by the analogy with perfect graphs. The decomposition theorems that are known for even-hole-free graphs are seemingly more powerful than the ones for perfect graphs: the basic classes and the decompositions are in some respect more restricted. But strangely, in an algorithmic perpective, much more is known for perfect graphs. For instance, coloring and finding a maximum stable set are open for even-hole-free graphs and polytime for perfect graphs. Also, it is very easy to provide perfect graphs of large treewidth and rankwidth, because of all bipartite graphs are perfect. For even-hole-free graphs, it is harder, but there are now several constructions, and the goal of the present talk is to survey all of them. On the way, we will give several open questions motivated by algorithms for even-hole-free graphs.  

Based on joint works with Isolde Adler, Chinh Hoang, Ngoc Khang Le, Haiko Muller, Marko Radovanovic, Ni Luh Dewi Sintiari and Kristina Vuskovic