t-perfection in P₅-free graphs

DOI10.1137/16M1059874MaRDI QIDQ5348215zbMATH OpenFDO

Authors Henning Bruhn, Elke Fuchs

Publication date 14 August 2017

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

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

zbMATH Keywords

stable set polytopenear-bipartiteantiweb\(P_5\)-free

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Perfect graphs (05C17)

Abstract: A graph is called $t$-perfect if its stable set polytope is fully described by non-negativity, edge and odd-cycle constraints. We characterise $P_5$-free $t$-perfect graphs in terms of forbidden $t$-minors. Moreover, we show that $P_5$-free $t$-perfect graphs can always be coloured with three colours, and that they can be recognised in polynomial time.

Recommendations

• On claw-free t-perfect graphs
• Characterising claw-free \(t\)-perfect graphs
• Claw-free \(t\)-perfect graphs can be recognized in polynomial time
• Claw-free \(t\)-perfect graphs can be recognised in polynomial time
• \(t\)-perfection is always strong for claw-free graphs

Cites work

• scientific article; zbMATH DE number 2079379 (Why is no real title available?)
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• A class of facet producing graphs for vertex packing polyhedra
• A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
• Anti-blocking polyhedra
• Antiwebs are rank-perfect
• Applying Lehman's theorems to packing problems
• Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
• Critical perfect graphs and perfect 3-chromatic graphs
• Geometric algorithms and combinatorial optimization
• Graph theory
• On 3-colorable \(P_5\)-free graphs
• On certain polytopes associated with graphs
• On claw-free t-perfect graphs
• On rank-perfect subclasses of near-bipartite graphs
• On the Chvàtal rank of linear relaxations of the stable set polytope
• Polytope des independants d'un graphe série-parallèle
• Relaxations of vertex packing
• The Graphs with All Subgraphs T-Perfect
• The stable set polytope and some operations on graphs
• The strong perfect graph theorem
• The structure of claw-free graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• \(K_{4}\)-free graphs with no odd holes

Cited in

(6)

• The perfect \(T (G)\)-triple system for each subgraph \(G\) of \(K_5\) with eight edges
• scientific article; zbMATH DE number 2227376 (Why is no real title available?)
• Strong T-Perfection of Bad-K₄ -Free Graphs
• Complementation in T-perfect graphs
• scientific article; zbMATH DE number 5545494 (Why is no real title available?)
• Characterising claw-free \(t\)-perfect graphs

This page was built for publication: \(t\)-perfection in \(P_5\)-free graphs

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