$t$-perfection in $P_5$-free graphs

Abstract

A graph is called $t$-perfect if its stable set polytope is fully described by non-negativity, edge and odd-cycle constraints. We characterise $P_5$-free $t$-perfect graphs in terms of forbidden $t$-minors. Moreover, we show that $P_5$-free $t$-perfect graphs can always be coloured with three colours, and that they can be recognised in polynomial time.

Work of Holm et al of which we were not aware made some parts unnecessary. This concerns mostly the section on near-bipartite graphs that is much shorter now