On box-perfect graphs

DOI10.1016/J.JCTB.2017.07.001MaRDI QIDQ1682206zbMATH OpenOpenAlexFDO

Authors Guoli Ding, Wenan Zang, Qiu-Lan Zhao

Publication date 28 November 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.04572, http://hdl.handle.net/10722/249653

zbMATH Keywords

perfect graphstructural characterizationbox-perfect graphbox-TDI systemTDI system

Mathematics Subject Classification ID

Perfect graphs (05C17)

Abstract: Let $G=(V,E)$ be a graph and let $A_G$ be the clique-vertex incidence matrix of $G$. It is well known that $G$ is perfect iff the system $A_{{}_G}mathbfxlemathbf1$, $mathbfxgemathbf0$ is totally dual integral (TDI). In 1982, Cameron and Edmonds proposed to call $G$ box-perfect if the system $A_{{}_G}mathbfxlemathbf1$, $mathbfxgemathbf0$ is box-totally dual integral (box-TDI), and posed the problem of characterizing such graphs. In this paper we prove the Cameron-Edmonds conjecture on box-perfectness of parity graphs, and identify several other classes of box-perfect graphs. We also develop a general and powerful method for establishing box-perfectness.

Recommendations

• A min-max relation for the partial q-colourings of a graph. II: Box perfection
• scientific article; zbMATH DE number 4059461
• Progress on perfect graphs
• The box-TDI system associated with 2-edge connected spanning subgraphs
• Near-perfect matrices

Cites work

• scientific article; zbMATH DE number 3851153 (Why is no real title available?)
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 554064 (Why is no real title available?)
• scientific article; zbMATH DE number 3390792 (Why is no real title available?)
• A description of claw-free perfect graphs
• A min-max relation for the partial q-colourings of a graph. II: Box perfection
• Characterization of Totally Unimodular Matrices
• Claw-free graphs. V. Global structure
• Coflow polyhedra
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Even pairs in Berge graphs
• Normal hypergraphs and the perfect graph conjecture
• On box totally dual integral polyhedra
• Parity Graphs
• Recognizing Berge graphs
• Some partitions associated with a partially ordered set
• The box-TDI system associated with 2-edge connected spanning subgraphs
• The strong perfect graph theorem
• The structure of Sperner k-families
• The structure of claw-free perfect graphs
• Transitiv orientierbare Graphen

Cited in

(12)

• scientific article; zbMATH DE number 4059461 (Why is no real title available?)
• scientific article; zbMATH DE number 5214885 (Why is no real title available?)
• On (2,3)-agreeable box societies
• scientific article; zbMATH DE number 1835115 (Why is no real title available?)
• A unified approach to box-Mengerian hypergraphs
• When is the matching polytope box-totally dual integral?
• Box-total dual integrality, box-integrality, and equimodular matrices
• A weak box-perfect graph theorem
• A min-max relation for the partial q-colourings of a graph. II: Box perfection
• Isolating a vertex via lattices: polytopes with totally unimodular faces
• The Schrijver system of the flow cone in series-parallel graphs
• Box-total dual integrality and edge-connectivity

This page was built for publication: On box-perfect graphs

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