Colloquium by Akiyoshi Tsuchiya (Osaka University): Polyhedral characterizations of perfect graphs
Perfect graphs are important objects in graph theory.
The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families.
One of the most famous and most important results is the strong perfect graph theorem conjectured by Claude Berge and proved by Chudnovsky, Robertson and Thomas. This theorem characterizes perfect graphs.
Our interest is to give other characterizations of perfect graphs.
In this talk, we construct several lattice polytopes arising from a finite simple graph and characterize when the graph is perfect in terms of the lattice polytopes.
This talk is based on joint work with Takayuki Hibi and Hidefumi Ohsugi.
Time & Location
Oct 22, 2018 | 04:00 PM s.t.
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
Room MA 041 (Ground Floor)