Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time

DOI10.1137/151006111zbMath1335.05071OpenAlexW2347101962MaRDI QIDQ2804992

Henning Bruhn, Oliver Schaudt

Publication date: 9 May 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/151006111

zbMATH Keywords

claw-free graphsinduced minors\(t\)-perfect graphs

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items

On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• On claw-free \(t\)-perfect graphs
• A class of h-perfect graphs
• The strong perfect graph theorem
• Polytope des independants d'un graphe série-parallèle
• The complexity of induced minors and related problems
• On certain polytopes associated with graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• Applying Lehman's theorems to packing problems
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Finding induced paths of given parity in claw-free graphs
• Solving the 2-disjoint paths problem in nearly linear time
• Recognizing Berge graphs
• Induced Disjoint Paths in Claw-Free Graphs
• t-Perfection Is Always Strong for Claw-Free Graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• The Graphs with All Subgraphs T-Perfect
• Compositions of Graphs and Polyhedra II: Stable Sets
• Perfect zero–one matrices
• Strong T-Perfection of Bad-K₄ -Free Graphs
• Algorithms for Perfectly Contractile Graphs
• The Graph Minor Algorithm with Parity Conditions