On box-perfect graphs

摘要

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)x = 1, x = 0 is totally dual integral (TDI). In 1982, Cameron and Edmonds proposed to call G box-perfect if the system A(G)x = 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. (C) 2017 Elsevier Inc. All rights reserved.