t-perfection in P₅-free graphs

2015/07/01 by Bruhn, Henning, Fuchs, Elke
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1507.00173

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₅-free t-perfect graphs in terms of forbidden t-minors. Moreover, we show that P₅-free t-perfect graphs can always be coloured with three colours, and that they can be recognised in polynomial time.

Related

• Claw-free t-perfect graphs can be recognised in polynomial time
• Colouring t-perfect graphs
• On Fork-free T-perfect Graphs
• Forbidden induced pairs for perfectness and ω-colourability of graphs
• Complementation in t-perfect graphs