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

DOI10.1137/151006111zbMATH Open1335.05071OpenAlexW2347101962MaRDI QIDQ2804992FDOQ2804992

Authors: 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

Recommendations

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Introduction to algorithms.
• On certain polytopes associated with graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• The strong perfect graph theorem
• Recognizing Berge graphs
• The disjoint paths problem in quadratic time
• Applying Lehman's theorems to packing problems
• Perfect zero–one matrices
• Algorithms for Perfectly Contractile Graphs
• The complexity of induced minors and related problems
• Kernels, stable matchings, and Scarf's lemma
• Solving the 2-disjoint paths problem in nearly linear time
• On claw-free \(t\)-perfect graphs
• Polytope des independants d'un graphe série-parallèle
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• The Graphs with All Subgraphs T-Perfect
• Compositions of Graphs and Polyhedra II: Stable Sets
• A class of h-perfect graphs
• Induced disjoint paths in claw-free graphs
• Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
• Strong T-Perfection of Bad-K₄ -Free Graphs
• The Graph Minor Algorithm with Parity Conditions
• Title not available (Why is that?)
• Finding induced paths of given parity in claw-free graphs
• \(t\)-perfection is always strong for claw-free graphs

Cited In (11)

• On claw-free \(t\)-perfect graphs
• Title not available (Why is that?)
• The \(\langle t \rangle \)-property of some classes of graphs
• \(t\)-perfection is always strong for claw-free graphs
• \(t\)-perfection in \(P_5\)-free graphs
• Claw-free \(t\)-perfect graphs can be recognised in polynomial time
• On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure
• Recognizing claw-free perfect graphs
• Title not available (Why is that?)
• Characterising claw-free \(t\)-perfect graphs
• Title not available (Why is that?)

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

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