On box-perfect graphs

DOI10.1016/J.JCTB.2017.07.001zbMATH Open1375.05111arXiv1608.04572OpenAlexW2964281897MaRDI QIDQ1682206FDOQ1682206

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)

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.

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

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

zbMATH Keywords

perfect graphstructural characterizationbox-perfect graphbox-TDI systemTDI system

Mathematics Subject Classification ID

Perfect graphs (05C17)

Cites Work

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

Cited In (12)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On \((2,3)\)-agreeable box societies
• Title not available (Why is that?)
• 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)