<figure><img src="image_1.png" /></figure>

HAL
open science

# A weak box-perfect graph theorem

Patrick Chervet, Roland Grappe

► To cite this version:

Patrick Chervet, Roland Grappe. A weak box-perfect graph theorem. Journal of Combinatorial Theory, Series B, 2024, 169, pp.367-372. 10.1016/j.jctb.2024.07.006. hal-04709997

HAL Id: hal-04709997

https://hal.science/hal-04709997v1

Submitted on 15 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A weak box-perfect graph theorem

Patrick Chervet<sup>a</sup>, Roland Grappe<sup>b,c</sup>

<figure><img src="image_3.png" /></figure>

## ARTICLE INFO

Article history:
Received 14 June 2023
Available online 30 July 2024

Keywords:
Perfect graphs
Box-perfect graphs
Complete join

## ABSTRACT

A graph $G$ is called *perfect* if $\omega(H) = \chi(H)$ for every induced subgraph $H$ of $G$, where $\omega(H)$ is the clique number of $H$ and $\chi(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 $\overline{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 $\overline{G}$ are box-perfect if and only if $\overline{G}^+$ is box-perfect, where $G^+$ is obtained by adding a universal vertex to $G$. Consequently, $G^+$ is box-perfect if and only if $\overline{G}^+$ is box-perfect. As a corollary, we characterize when the complete join of two graphs is box-perfect.

© 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

In a graph, a *clique* is a set of pairwise adjacent vertices, and a *stable set* is a set of pairwise nonadjacent vertices. The *stable set polytope* $S(G)$ of a graph $G$ is the convex hull of the incidence vectors of its stable sets. A graph $G$ is called *perfect* if $\omega(H) = \chi(H)$ for every induced subgraph $H$ of $G$, where $\omega(H)$ is the clique number and $\chi(H)$ the chromatic number of $H$. Lovász [9] proved the Weak Perfect Graph The-

<footnote><sup>a</sup> Lycée Olympe de Gouges, Noisy le Sec, France</footnote>

<footnote><sup>b</sup> Université Paris Dauphine, PSL Research University, LAMSADE, CNRS UMR 7243, Paris, France</footnote>

<footnote><sup>c</sup> Université Sorbonne Paris-Nord, LIPN, CNRS UMR 7030, Villetaneuse, France</footnote>

<footnote>E-mail addresses: pat.chervet@gmail.com (P. Chervet), roland.grappe@lamsade.dauphine.fr
(R. Grappe).</footnote>
orem, which states that a graph $G$ is perfect if and only if its complement $\bar{G}$ is perfect. It is also known [4,8] that perfect graphs are the graphs whose stable set polytope is described by the system composed of the clique inequalities and the nonnegativity constraints:

$$ \left\{ \begin{array}{l} \sum_{v \in C} x_v \le 1 \quad \text{for each maximal clique } C \text{ of } G, \\ x \ge 0. \end{array} \right. \qquad (1) $$

In fact, system (1) is totally dual integral if and only if $G$ is perfect. A rational system of linear inequalities $Ax \le b$ is totally dual integral (TDI) if the minimization problem in the linear programming duality:

$$ \max\{c^\top x : Ax \le b\} = \min\{b^\top y : A^\top y = c, y \ge 0\} $$

admits an integer optimal solution for each integer vector $c$ such that the maximum is finite. A system $Ax \le b$ is box-totally dual integral [7] (box-TDI) if $Ax \le b$, $\ell \le x \le u$ is TDI for all rational vectors $\ell$ and $u$ (with possible infinite components), and box-TDI polyhedra [5] are those that can be described by a box-TDI system. TDI and box-TDI systems were introduced in the late 1970's and serve as a general framework for establishing various min-max relations in combinatorial optimization [10].

A box-perfect graph is a graph for which system (1) is box-TDI. Equivalently, a graph is box-perfect if and only if it is perfect and its stable set polytope is box-TDI. The characterization of box-perfect graphs is a longstanding open question raised by Cameron and Edmonds in 1982 [1]. Mix-max relations about box-perfect graphs are discussed in [2]. Recent progress has been made on this topic by Ding, Zang, and Zhao [6]. They exhibit several new subclasses of perfect graphs and in particular prove the conjecture of Cameron and Edmonds [1] that parity graphs are box-perfect.

The Weak Perfect Graph Theorem does not hold for box-perfect graphs, as shown by $S_3$ below, which is not box-perfect (see e.g. [3, Section 6.2]) but whose complement $\bar{S}_3$ is. Adding a universal vertex $u^+$ to this complement destroys its box-perfection, that is, $\bar{S}_3^+$ is not box-perfect. Here, $G^+$ denotes the graph obtained from a graph $G$ by adding a universal vertex, which is a new vertex connected to all the vertices of $G$.

<figure><img src="image_4.png" /></figure>
We prove here that this holds in general. More precisely, we prove the following.

**Theorem 1.** Given a graph $G = (V, E)$, the following statements are equivalent.

1. Both $G$ and $\bar{G}$ are box-perfect,

2. $\bar{G}^+$ is box-perfect,

3. $G^+$ is box-perfect.

Our starting point builds upon recent characterizations of box-TDI polyhedra [3]. In the context of box-perfect graphs, the combination of [3, Theorem 2] and [3, Observation 4] yields Theorem 2 below, for which a few definitions are required.

A subset $U$ of $V$ is also viewed as the row vector $(\chi^U)^\top$, where $\chi^U \in \{0, 1\}^V$ denotes the incidence vector of $U$. A set of subsets of $V$ is then viewed as a matrix whose rows correspond to those subsets. For a set $C$ of columns and a set $R$ of rows of a matrix $M$, we denote by $M^C$ the submatrix of $M$ formed by the columns in $C$, and by $M_R$ and the submatrix of $M$ formed by the rows in $R$.

A rational $r \times n$ matrix is *equimodular* if it has full row rank and its nonzero $r \times r$ determinants all have the same absolute value. A *face-defining pair* of a graph $G$ is a pair $(\mathcal{K}, \mathcal{S})$, where $\mathcal{K}$ is a set of linearly independent cliques, $\mathcal{S}$ is a set of affinely independent stable sets, each clique of $\mathcal{K}$ intersects each stable set of $\mathcal{S}$, and<fnref n="1" /> $|\mathcal{K}| + |\mathcal{S}| = |V| + 1$. Such a pair is *equimodular* when the matrix whose rows are the cliques of $\mathcal{K}$ is equimodular. Equivalently, as explained below, the matrix whose rows are $(\chi^T - \chi^S)^\top$, $T \in \mathcal{S} \setminus \{\mathcal{S}\}$ is equimodular for each<fnref n="2" /> $S \in \mathcal{S}$.

**Theorem 2.** A perfect graph is box-perfect if and only if all its face-defining pairs are equimodular.

A face-defining matrix<fnref n="3" /> of a polyhedron $P = \{x : Ax \le b\}$ is a linearly independent set $A_R$ of rows of $A$ such that the affine hull of some face $F$ of $P$ can be written $\{x : A_R x = b_R\}$. [3, Theorem 2] asserts that a polyhedron is box-TDI if and only if all its face-defining matrices are equimodular. By [3, Observation 4], the cardinality and independence conditions on a face-defining pair $(\mathcal{K}, \mathcal{S})$ ensure that $\mathcal{K}$ is face-defining for the stable set polytope. When the graph is perfect, the face-defining pairs encode all the face-defining matrices of system (1) without nonnegativity constraints. The fact that nonnegativity constraints need not be considered in Theorem 2 relies on the following: if $F \cap \{x \ge 0\}$ is not box-TDI for some face $F$ of $P$, then neither is $F$.

We will use that a face-defining pair $(\mathcal{K}, \mathcal{S})$ is equimodular if and only if the matrix whose rows are $(\chi^T - \chi^S)^\top$, $T \in \mathcal{S} \setminus \{\mathcal{S}\}$ is equimodular for each $S \in \mathcal{S}$. Indeed,

<footnote n="1">¹ At this point, $|\mathcal{K}| + |\mathcal{S}| \le |V| + 1$ always holds by geometric arguments.</footnote>

<footnote n="2">² Here, each can be replaced by some, see [3, Corollary 6].</footnote>

<footnote n="3">³ Compared to [3], face-defining matrices here are “from the system”. It is implicit therein that [3, Theorem 2] also holds under these settings.</footnote>
when $(\mathcal{K}, \mathcal{S})$ is a face-defining pair, $\mathcal{K}$ is a face-defining matrix of the affine hull of $\mathcal{S}$. By [3, Theorem 2], since the latter has only itself as a face, it is box-TDI if and only if $\mathcal{K}$ is equimodular. Statements 2 and 3 of [3, Corollary 6] imply the announced equivalence as the vectors $(\chi^T - \chi^S)$ for $T \in \mathcal{S} \setminus \{\mathcal{S}\}$ form a basis of the associated linear space, for each $\mathcal{S} \in \mathcal{S}$.

Note that box-perfection is preserved under taking induced subgraphs [2]. Besides, each clique in a face-defining pair can be assumed maximal, because it can be assumed maximal in system (1). We can now prove Theorem 1.

**Proof of Theorem 1.** Replacing $G$ by $\bar{G}$ shows that it is enough to prove (2 $\Rightarrow$ 1) and (1 $\Rightarrow$ 3). Moreover, $G, \bar{G}, G^+$, and $\bar{G}^+$ are all perfect as long as one of them is, hence we just have to deal with the box-TDIness of their stable set polytopes. Let $u^+$ denote the universal vertex of $G^+$ and $\bar{u}^+$ that of $\bar{G}^+$.

(2 $\Rightarrow$ 1) Suppose that $\bar{G}^+$ is box-perfect. Then, so is $\bar{G} = \bar{G}^+ \setminus \{\bar{u}^+\}$. To prove that $G$ is box-perfect, by Theorem 2, we show that every face-defining pair $(\mathcal{K}, \mathcal{S})$ of $G$ is equimodular.

Each element of $\bar{\mathcal{K}} = \{S \cup \{\bar{u}^+\} : S \in \mathcal{S}\}$ is a clique of $\bar{G}^+$ and each element of $\bar{\mathcal{S}} = \mathcal{K} \cup \{\{\bar{u}^+\}\}$ is a stable set of $\bar{G}^+$. Let us prove that $(\bar{\mathcal{K}}, \bar{\mathcal{S}})$ forms a face-defining pair of $\bar{G}^+$. Firstly, $\bar{\mathcal{K}}$ is linearly independent because $\mathcal{S}$ is affinely independent and $\bar{\mathcal{K}}$ is obtained from $\mathcal{S}$ by adding a **1** column. Secondly, $\bar{\mathcal{S}}$ is affinely independent because it is linearly independent. Thirdly, each stable set of $\bar{\mathcal{S}}$ intersects each clique of $\bar{\mathcal{K}}$. Finally, $|\bar{\mathcal{K}}| + |\bar{\mathcal{S}}| = |V| + \{\bar{u}^+\}| + 1$, thus $(\bar{\mathcal{K}}, \bar{\mathcal{S}})$ forms a face-defining pair of $\bar{G}^+$.

By Theorem 2, $(\bar{\mathcal{K}}, \bar{\mathcal{S}})$ is equimodular, and so is the matrix whose rows are $(\chi^K - \chi^{\{\bar{u}^+\}})^\top$, for all $K \in \bar{\mathcal{S}} \setminus \{\{\bar{u}^+\}\}$. Removing $\bar{u}^+$'s column from this matrix yields $\mathcal{K}$, hence $(\mathcal{K}, \mathcal{S})$ is equimodular.

(1 $\Rightarrow$ 3) Suppose that $G$ and $\bar{G}$ are both box-perfect, and let $(\mathcal{K}^+, \mathcal{S}^+)$ be a face-defining pair of $G^+$ with $r$ cliques in $\mathcal{K}^+$. We may assume that each clique of $\mathcal{K}^+$ is maximal, hence each of them contains $u^+$. In particular, $(\mathcal{K}^+)^{\{u^+\}} = \mathbf{1}$ and we may assume that $\{\{u^+\}\} \subsetneq \mathcal{S}^+$. Let $\mathcal{K} = \{K \setminus \{u^+\} : K \in \mathcal{K}^+\}$ and $\mathcal{S} = \mathcal{S}^+ \setminus \{\{u^+\}\}$.

Let us prove that $(\mathcal{K}, \mathcal{S})$ forms a face-defining pair of $G$. In $\mathcal{K}^+$, column $u^+$ is a linear combination of the columns of $\mathcal{K}$, because $\mathcal{K}\chi^S = \mathbf{1}$ for $S \in \mathcal{S}$. Thus, the linear independence of $\mathcal{K}^+$ implies that of $\mathcal{K}$. The affine independence of $\mathcal{S}$ comes from that of $\mathcal{S}^+$. Since no stable set of $\mathcal{S}$ contains $u^+$, each $S \in \mathcal{S}$ intersects each $K \in \mathcal{K}$. Finally, $|\mathcal{K}| + |\mathcal{S}| = |V| + 1$. Since $G$ is box-perfect, $(\mathcal{K}, \mathcal{S})$ is equimodular by Theorem 2. Therefore, all the $r \times r$ nonzero determinants of $\mathcal{K}^+$ not containing column $u^+$ have the same absolute value.

Recall that cliques and stable sets of $G$ are respectively stable sets and cliques of $\bar{G}$, and let us prove that $(\mathcal{S}, \mathcal{K})$ forms a face-defining pair of $\bar{G}$. From the last paragraph, all that remains to show is the linear independence of $\mathcal{S}$, which holds because $\mathcal{S}$ is affinely independent and $\mathcal{S}\chi^K = \mathbf{1}$ for $K \in \mathcal{K}$. Since $\bar{G}$ is box-perfect, $(\mathcal{S}, \mathcal{K})$ is equimodular by Theorem 2. Therefore, for some $K \in \mathcal{K}$, so is the matrix whose rows are $(\chi^L - \chi^K)^\top$.
for all $L \in \mathcal{K} \setminus \{K\}$. This matrix is obtained by pivoting in $\mathcal{K}^+$ using $L$'s row in $u^+$'s column, hence all the $r \times r$ nonzero determinants of $\mathcal{K}^+$ containing column $u^+$ have the same absolute value.

To prove that $(\mathcal{K}^+, \mathcal{S}^+)$ is equimodular, all that remains to show is that $|\det(B)| = |\det(C)|$ for some nonsingular $r \times r$ submatrices $B$ and $C$ of $\mathcal{K}^+$ with column $u^+$ in exactly one of them. For $S \in \mathcal{S}$, the columns of $\mathcal{K}^S$ are linearly independent. Since $\mathcal{K}$ has full row rank, $\mathcal{K}^S$ can be completed into a nonsingular $r \times r$ submatrix $B$ of $\mathcal{K}$. The sum of the columns of $B$ associated with $S$ is 1, hence replacing one of them by 1 does not change the determinant. Reordering the columns provides the desired matrix $C$. $\blacksquare$

The complete join of two graphs $G$ and $H$ is the graph obtained by connecting each vertex of $G$ to each vertex of $H$. This operation preserves perfection, but not box-perfection. Indeed, $\overline{S_3}^+$ is not box-perfect and is the complete join of two box-perfect graphs, namely $\overline{S_3}$ and a single vertex $\{u\}$.

**Corollary 3.** The complete join of $G$ and $H$ is box-perfect if and only if both $G^+$ and $H^+$ are box-perfect.

**Proof.** Let $J$ be the complete join of $G$ and $H$. If $J$ is box-perfect, then $G^+$ and $H^+$, as induced subgraphs of $J$, are also box-perfect. Conversely, suppose that $G^+$ and $H^+$ are box-perfect. Equivalently, by Theorem 1, $\overline{G}^+$ and $\overline{H}^+$ are box-perfect. Note that $\overline{J}^+$ is the graph obtained from $\overline{G}^+$ and $\overline{H}^+$ by identifying their universal vertex $u$. Let us prove that $\overline{J}^+$ is box-perfect. Then so is $J$ by Theorem 1, and the proof is done.

By contradiction, suppose that $\overline{J}^+$ is not box-perfect, and let $(\mathcal{K}, \mathcal{S})$ be a nonequimodular face-defining pair of $\overline{J}^+$ given by Theorem 2. We may assume that each clique of $\mathcal{K}$ is maximal, and then $u$ belongs to each of them. Given the structure of the graph, $\mathcal{K}$ is composed of cliques $\mathcal{K}_G$ and $\mathcal{K}_H$ of respectively $\overline{G}^+$ and $\overline{H}^+$, with $\mathcal{K}_G \cap \mathcal{K}_H = \{u\}$ for all $\mathcal{K}_G \in \mathcal{K}_G$ and $\mathcal{K}_H \in \mathcal{K}_H$. The latter implies that each nonzero $|\mathcal{K}| \times |\mathcal{K}|$ determinant of $\mathcal{K}$ is the product of a nonzero $|\mathcal{K}_G| \times |\mathcal{K}_G|$ determinant of $\mathcal{K}_G$ by a nonzero $|\mathcal{K}_H| \times |\mathcal{K}_H|$ determinant of $\mathcal{K}_H$. Since $\mathcal{K}$ is not equimodular, at least one of $\mathcal{K}_G$ and $\mathcal{K}_H$ is not equimodular.

Let $\mathcal{S}_G$ be a maximal family of affinely independent stables sets of $\overline{G}$ distinct from $\{u\}$ and intersecting each clique of $\mathcal{K}_G$. Define $\mathcal{S}_H$ similarly. Take $\mathcal{S}_G \in \mathcal{S}_G$ and $\mathcal{S}_H \in \mathcal{S}_H$ and let $\mathcal{S}' = \{\{u\}\} \cup \{\mathcal{S} \cup \mathcal{S}_H \text{ for all } \mathcal{S} \in \mathcal{S}_G\} \cup \{\mathcal{S}_G \cup \mathcal{S} \text{ for all } \mathcal{S} \in \mathcal{S}_H\}$. Given the structure of the graph, a dimensional analysis shows that $(\mathcal{K}, \mathcal{S}')$, $(\mathcal{K}_G, \{u\} \cup \mathcal{S}_G)$, and $(\mathcal{K}_H, \{u\} \cup \mathcal{S}_H)$ are respectively face-defining pairs of $\overline{J}^+$, $\overline{G}^+$, and $\overline{H}^+$. This contradicts the fact that $\overline{G}^+$ and $\overline{H}^+$ are box-perfect. $\blacksquare$

We mention that the arguments of the last two paragraphs can be adapted to prove that a graph is box-perfect if and only if all its 2-connected components are box-perfect.
## Data availability

No data was used for the research described in the article.

## Acknowledgments

We thank the anonymous reviewers for their very careful reading and their valuable comments.

## References

[1] K. Cameron, Polyhedral and algorithmic ramifications of antichains, Ph.D. Thesis, University of Waterloo, 1982, Supervisor: J. Edmonds.

[2] K. Cameron, A min-max relation for the partial q-colourings of a graph. Part II: Box perfection, Discrete Math. 74 (1) (1989) 15-27.

[3] P. Chervet, R. Grappe, L.-H. Robert, Box-total dual integrality, box-integrality, and equimodular matrices, Math. Program. 188 (1) (2021) 319-349.

[4] V. Chvátal, On certain polytopes associated with graphs, J. Comb. Theory, Ser. B 18 (2) (1975) 138-154.

[5] W. Cook, On box totally dual integral polyhedra, Math. Program. 34 (1) (1986) 48-61.

[6] G. Ding, W. Zang, Q. Zhao, On box-perfect graphs, J. Comb. Theory, Ser. B 128 (2018) 17-46.

[7] J. Edmonds, R. Giles, A min-max relation for submodular functions on graphs, in: P. Hammer, E. Johnson, B. Korte, G. Nemhauser (Eds.), Studies in Integer Programming, in: Annals of Discrete Mathematics, vol. 1, Elsevier, 1977, pp. 185-204.

[8] D. Fulkerson, Anti-blocking polyhedra, J. Comb. Theory, Ser. B 12 (1) (1972) 50-71.

[9] L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (3) (1972) 253-267.

[10] A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, 1999.