On claw-free t-perfect graphs

DOI10.1007/S10107-010-0436-9MaRDI QIDQ431021zbMATH OpenOpenAlexFDO

Authors Henning Bruhn, Maya Stein

Publication date 26 June 2012

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-010-0436-9

zbMATH Keywords

polynomial-time algorithm3-colourable graphschromatic number of claw-free \(h\)-perfect graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph minors (05C83) Perfect graphs (05C17)

Recommendations

• Characterising claw-free t-perfect graphs
• The structure of claw-free perfect graphs
• On the choosability of claw-free perfect graphs
• A description of claw-free perfect graphs
• A characterization of claw-free \(b\)-perfect graphs
• On the choice number of claw-free perfect graphs
• Clique-perfectness of claw-free planar graphs
• Claw-free t-perfect graphs can be recognized in polynomial time
• Claw-free \(t\)-perfect graphs can be recognised in polynomial time
• Strongly perfect claw‐free graphs—A short proof

Cites work

• scientific article; zbMATH DE number 49899 (Why is no real title available?)
• scientific article; zbMATH DE number 3496213 (Why is no real title available?)
• scientific article; zbMATH DE number 3437188 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A class of h-perfect graphs
• Anti-blocking polyhedra
• Applying Lehman's theorems to packing problems
• Blocking and anti-blocking pairs of polyhedra
• Coloring quasi-line graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Compositions of Graphs and Polyhedra II: Stable Sets
• Geometric algorithms and combinatorial optimization
• Maximum matching and a polyhedron with 0,1-vertices
• On certain polytopes associated with graphs
• On the stable set polytope of a series-parallel graph
• Polyhedral characterizations and perfection of line graphs
• Polytope des independants d'un graphe série-parallèle
• Recognizing Berge graphs
• Relaxations of vertex packing
• Stable Set Polytopes for a Class of Circulant Graphs
• The Graphs with All Subgraphs T-Perfect
• The Two-Triangle Case of the Acquaintance Graph
• The ellipsoid method and its consequences in combinatorial optimization
• The rank facets of the stable set polytope for claw-free graphs
• The stable set polytope of quasi-line graphs
• The strong perfect graph theorem
• The structure of claw-free graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs

Cited in

(15)

• Claw-free graphs with strongly perfect complements. Fractional and integral version. II: Nontrivial strip-structures
• On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets
• The \(\langle t \rangle \)-property of some classes of graphs
• Point partition numbers: perfect graphs
• Strongly perfect claw‐free graphs—A short proof
• \(t\)-perfection is always strong for claw-free graphs
• \(t\)-perfection in \(P_5\)-free graphs
• On the choice number of claw-free perfect graphs
• Integer round-up property for the chromatic number of some \(h\)-perfect graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• scientific article; zbMATH DE number 5304940 (Why is no real title available?)
• Claw-free \(t\)-perfect graphs can be recognised in polynomial time
• Complementation in T-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: On claw-free \(t\)-perfect graphs

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