A family of counterexamples for a conjecture of Berge on -diperfect digraphs

DOI10.1016/J.DISC.2023.113458MaRDI QIDQ6041566zbMATH OpenOpenAlexWikidataFDO

Authors Caroline Aparecida de Paula Silva, Cândida Nunes da Silva, Orlando Lee

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.08007

zbMATH Keywords

alpha-diperfect digraphsdigraphspath partitionstable set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $D$ be a digraph. A stable set $S$ of $D$ and a path partition $mathcalP$ of $D$ are orthogonal if every path $PinmathcalP$ contains exactly one vertex of $S$. In 1982, Berge defined the class of $alpha$-diperfect digraphs. A digraph $D$ is $alpha$-diperfect if for every maximum stable set $S$ of $D$ there is a path partition $mathcalP$ of $D$ orthogonal to $S$ and this property holds for every induced subdigraph of $D$. An anti-directed odd cycle is an orientation of an odd cycle $(x_0,ldots,x_{2k},x_0)$ with $kgeq2$ in which each vertex $x_0,x_1,x_2,x_3,x_5,x_{7}ldots,x_{2k-1}$ is either a source or a sink. Berge conjectured that a digraph $D$ is $alpha$-diperfect if and only if $D$ does not contain an anti-directed odd cycle as an induced subdigraph. In this paper, we show that this conjecture is false by exhibiting an infinite family of orientations of complements of odd cycles with at least seven vertices that are not $alpha$-diperfect.

Recommendations

• \(\alpha\)-diperfect digraphs
• Some results on Berge's conjecture and begin-end conjecture
• \( \chi \)-diperfect digraphs
• scientific article; zbMATH DE number 3891403
• On kernels in perfect graphs

Cites work

• \(\alpha\)-diperfect digraphs
• Diperfect graphs
• Graph theory
• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• Some results on Berge's conjecture and begin-end conjecture
• The strong perfect graph theorem

Cited in

(6)

• On the non-existence of families of \((d,k, \delta)\)-digraphs containing only selfrepeat vertices
• \(\alpha\)-diperfect digraphs
• \( \chi \)-diperfect digraphs
• Some results on Berge's conjecture and begin-end conjecture
• BE-diperfect digraphs with stability number two
• A family of counterexamples to begin-end conjecture

This page was built for publication: A family of counterexamples for a conjecture of Berge on \(\alpha\)-diperfect digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041566)