Colouring t-perfect graphs
| Autor: | Chudnovsky, Maria, Cook, Linda, Davies, James, Oum, Sang-il, Tan, Jane |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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\'{a}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 $\omega$ is $(\omega + 199050)$-colourable. Comment: 23 pages, 4 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|