Paper Info
Title
On box-perfect graphs.
Abstract
Let G=(V,E) be a graph and let AG be the clique-vertex incidence matrix of G. It is well known that G is perfect iff the system AGx≤1, x≥0 is totally dual integral (TDI). In 1982, Cameron and Edmonds proposed to call G box-perfect if the system AGx≤1, x≥0 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.
Year
DOI
Venue
2018
10.1016/j.jctb.2017.07.001
Journal of Combinatorial Theory, Series B
Keywords
DocType
Volume
Perfect graph,Box-perfect graph,TDI system,Box-TDI system,Structural characterization
Journal
128
ISSN
Citations 
PageRank 
0095-8956
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Guoli Ding144451.58
Wenan Zang230539.19
Qiulan Zhao322.08