2024/12/23 by Maria Chudnovsky, L. F. Cook, Chudnovsky, Maria +7 · 1 voice
Computer Science · Engineering · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2412.17735
Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities (including edge inequalities). In 1975, Chvátal defined an analogous class of t-perfect graphs, which are the graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. We show that t-perfect graphs are 199053-colourable. This is the first finite bound on the chromatic number of t-perfect graphs and answers a question of Shepherd from 1995. Our proof also shows that every h-perfect graph with clique number ω is (ω+ 199050)-colourable.