Colloquium by Akiyoshi Tsuchiya (Osaka University): Polyhedral characterizations of perfect graphs

Oct 22, 2018 | 04:00 PM s.t.

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
10623 Berlin
Room MA 041 (Ground Floor)
Campus map

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)