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.