Some results on Berge's conjecture and begin-end conjecture

DOI10.1007/S00373-022-02509-8zbMATH Open1491.05091arXiv2111.12168OpenAlexW3217070032WikidataQ113905204 ScholiaQ113905204MaRDI QIDQ2145686FDOQ2145686

Orlando Lee, Lucas Ismaily Bezerra Freitas

Publication date: 17 June 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Let $D$ be a digraph. A subset $S$ of $V(D)$ is a stable set if every pair of vertices in $S$ is non-adjacent in $D$. A collection of disjoint paths $mathcalP$ of $D$ is a path partition of $V(D)$, if every vertex in $V(D)$ is on a path of $mathcalP$. We say that a stable set $S$ and a path partition $mathcalP$ are orthogonal if each path of $P$ contains exactly one vertex of $S$. A digraph $D$ satisfies the $alpha$-property if for every maximum stable set $S$ of $D$, there exists a path partition $mathcalP$ such that $S$ and $mathcalP$ are orthogonal. A digraph $D$ is $alpha$-diperfect if every induced subdigraph of $D$ satisfies the $alpha$-property. In 1982, Claude Berge proposed a characterization of $alpha$-diperfect digraphs in terms of forbidden anti-directed odd cycles. In 2018, Sambinelli, Silva and Lee proposed a similar conjecture. A digraph $D$ satisfies the Begin-End-property or BE-property if for every maximum stable set $S$ of $D$, there exists a path partition $mathcalP$ such that (i) $S$ and $mathcalP$ are orthogonal and (ii) for each path $PinmathcalP$, either the start or the end of $P$ lies in $S$. A digraph $D$ is BE-diperfect if every induced subdigraph of $D$ satisfies the BE-property. Sambinelli, Silva and Lee proposed a characterization of BE-diperfect digraphs in terms of forbidden blocking odd cycles. In this paper, we show some structural results for $alpha$-diperfect and BE-diperfect digraphs. In particular, we show that in every minimal counterexample $D$ to both conjectures, the size of a maximum stable set is smaller than $vertV(D)vert/2$. As an application we use these results to prove both conjectures for arc-locally in-semicomplete and arc-locally out-semicomplete digraphs.

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

zbMATH Keywords

Berge's conjecturearc-locally in-semicomplete digraphbegin-end conjecture

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The strong perfect graph theorem
• Spectral Theory and Analysis
• TWO THEOREMS IN GRAPH THEORY
• The structure of strong arc-locally in-semicomplete digraphs
• Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs
• A classification of arc-locally semicomplete digraphs
• A classification of all arc-locally semicomplete digraphs
• Critical kernel imperfect problem in generalizations of bipartite tournaments
• \(\alpha\)-diperfect digraphs

Cited In (2)

• BE-diperfect digraphs with stability number two
• A family of counterexamples for a conjecture of Berge on \(\alpha\)-diperfect digraphs

This page was built for publication: Some results on Berge's conjecture and begin-end conjecture

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