A min-max relation for the partial q- colourings of a graph. Part II: Box perfection

AbstractThis paper examines extensions of a min-max equality (stated in C Berge, Part I) for the maximum number of nodes in a perfect graph which can be q-coloured.A system L of linear inequalities in the variables x is called TDI if for every linear function cx such that c is all integers, the dual of the linear program: maximize {cx: x satisfies L} has an integer-valued optimum solution or no optimum solution. A system L is called box TDI if L together with any inequalities l⩽x⩽u is TDI. It is a corollary of work of Fulkerson and Lov́asz that: where A is a 0–1 matrix with no all-0 column and with the 1-columns of any row not a proper subset of the 1-columns of any other row, the system L(G) = {Ax⩽1, x⩾0} is TDI if and only if A is the matrix of maximal cliques (rows) versus nodes (columns) of a perfect graph. Here we will describe a class of graphs in a graph-theoretic way, and characterize them as the graphs G for which the system L(G) is box TDI. Thus we call these graphs box perfect. We also describe some classes of box perfect graphs