Claw-Free t-Perfect Graphs Can Be Recognised in Polynomial Time

摘要

A graph is called t-perfect if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We show that it can be decided in polynomial time whether a given claw-free graph is t-perfect.