Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	操宜新，香港理工大学
Inviter:	陈旭瑾
Title:	T-perfect Graphs: Known and Unknown
Language:	Chinese& English
Time & Venue:	2023.07.29 10:00-11:00 南楼N620
Abstract:	Perfect graphs have been pivotal in graph theory. Although the definition is purely graph-theoretical, Chvátal noticed that they can be characterized by their independent set polytopes. This motivated him to propose a similar polytope that comprises nonnegativity, edge, and odd-cycle constraints. A graph is t-perfect if this polytope is the independent set polytope of the graph. We start with briefly surveying known results, including minimally t-imperfect graphs and characterizations of t-perfect that are claw-free, P5-free, or fork-free. We then discuss several conjectures that may lead to the final understanding of t-perfect graphs.