t-perfection in P₅-free graphs
classification
🧮 math.CO
keywords
freegraphsperfectalwayscalledcharacterisecolouredcolours
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.