제목: Bounding the chromatic number of t-perfect graphs
일시: 2024년 9월 25일(수) 오후 4:30
장소: 자연과학관 202호
연사: 엄상일 교수 (IBS Discrete Mathematics group)
초록:
Perfect graphs can be described as the graphs whose stable set polytope is defined by their non-negativity and clique inequalities (including edge inequalities). In 1975, Chvátal defined an analogous class called t-perfect graphs, which are the graphs whose stable set polytope is defined by their non-negativity, edge and odd circuit inequalities. We show that t-perfect graphs are 149295-colourable. This is the first finite bound on the chromatic number of t-perfect graphs, and answers a question of Shephard from 1995.
This is joint work with Maria Chudnovsky, Linda Cook, James Davies, and Jane Tan.
 |
|
|
