On claw-free \(t\)-perfect graphs

DOI10.1007/s10107-010-0436-9zbMath1245.05055OpenAlexW1989312278MaRDI QIDQ431021

Henning Bruhn, Maya Jakobine 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

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

Related Items

Integer round-up property for the chromatic number of some \(h\)-perfect graphs ⋮ Complementation in T-perfect graphs ⋮ $t$-Perfection in $P_5$-Free Graphs ⋮ Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time ⋮ On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets ⋮ Characterising claw-free t-perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of h-perfect graphs
• The strong perfect graph theorem
• The stable set polytope of quasi-line graphs
• Relaxations of vertex packing
• On the stable set polytope of a series-parallel graph
• Polytope des independants d'un graphe série-parallèle
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• The rank facets of the stable set polytope for claw-free graphs
• Polyhedral characterizations and perfection of line graphs
• On certain polytopes associated with graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Applying Lehman's theorems to packing problems
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Recognizing Berge graphs
• Anti-blocking polyhedra
• Coloring quasi-line 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
• Stable Set Polytopes for a Class of Circulant Graphs
• Maximum matching and a polyhedron with 0,1-vertices
• The Two-Triangle Case of the Acquaintance Graph
• Blocking and anti-blocking pairs of polyhedra