Claw-free t-perfect graphs can be recognised in polynomial time

DOI10.1007/978-3-319-07557-0_34MaRDI QIDQ5419013zbMATH OpenOpenAlexFDO

Authors Henning Bruhn, Oliver Schaudt

Publication date 2 June 2014

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.8186

zbMATH Keywords

claw-free graphsrecognition algorithm\(t\)-perfect graphsinduced minors

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Abstract: 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.

Recommendations

• Claw-free \(t\)-perfect graphs can be recognized in polynomial time
• On claw-free t-perfect graphs
• Characterising claw-free \(t\)-perfect graphs
• \(t\)-perfection is always strong for claw-free graphs
• scientific article; zbMATH DE number 1753165

Cited in

(7)

• On claw-free t-perfect graphs
• \(t\)-perfection is always strong for claw-free graphs
• \(t\)-perfection in \(P_5\)-free graphs
• Integer round-up property for the chromatic number of some \(h\)-perfect graphs
• Recognizing claw-free perfect graphs
• Claw-free \(t\)-perfect graphs can be recognized in polynomial time
• Characterising claw-free \(t\)-perfect graphs

This page was built for publication: Claw-free \(t\)-perfect graphs can be recognised in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419013)