BE-diperfect digraphs with stability number two

Caroline A. de Paula Silva¹ ; Cândida Nunes da Silva ; Orlando Lee

¹University of Campinas

The electronic journal of combinatorics, Tome 31 (2024) no. 2

Résumé

In 1982, Berge defined the class of $\alpha$-diperfect digraphs. A digraph $D$ is $\alpha$-diperfect if every induced subdigraph of $H$ of $D$ satisfies the following property: for every maximum stable set $S$ of $H$ there is a path partition $\mathcal{P}$ of $H$ in which every $P \in \mathcal{P}$ contains exactly one vertex of $S$. Berge conjectured a characterization of $\alpha$-diperfect digraphs by forbidding induced orientations of odd cycles. In 2018, Sambinelli, Nunes da Silva and Lee proposed a similar class of digraphs. A digraph $D$ is BE-diperfect if every induced subdigraph $H$ of $D$ satisfies the following property: for every maximum stable set $S$ of $H$ there is a path partition $\mathcal{P}$ of $H$ in which (i) every $P \in \mathcal{P}$ contains exactly one vertex of $S$ and (ii) $P$ either begins or ends at a vertex of $S$. They also conjectured that the BE-diperfect digraphs can be characterized by forbidding induced orientations of odd cycles; we refer to this as the Begin-End Conjecture. In 2023, de Paula Silva, Nunes da Silva and Lee presented an infinite family of counterexamples with stability number two to Berge's Conjecture. On the other hand, these digraphs are not counterexamples to the Begin-End Conjecture. In this paper, we prove that the latter conjecture holds for digraphs with stability number two.

Détail

DOI : 10.37236/12828

Classification : 05C20, 05C75
Mots-clés : path-partition, optimal coloring, anti-directed odd cycle, stability number, maximum stable set