A graph G is called perfect if ω(H)=χ(H) for every induced subgraph H of G, where ω(H) is the clique number of H and χ(H) its chromatic number. The Weak Perfect Graph Theorem of Lovász states that a graph G is perfect if and only if its complement G‾ is perfect. This does not hold for box-perfect graphs, which are the perfect graphs whose stable set polytope is box-totally dual integral. We prove that both G and G‾ are box-perfect if and only if G‾+ is box-perfect, where G+ is obtained by adding a universal vertex to G. Consequently, G+ is box-perfect if and only if G‾+ is box-perfect. As a corollary, we characterize when the complete join of two graphs is box-perfect.
No takes yet. Share an insight, caveat, or question.
Chervet et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: