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

DOI10.1007/S00373-022-02509-8MaRDI QIDQ2145686zbMATH OpenOpenAlexWikidataFDO

Authors Lucas Ismaily Bezerra Freitas, Orlando Lee

Publication date 17 June 2022

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

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)

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.

Recommendations

• \(\alpha\)-diperfect digraphs
• A family of counterexamples for a conjecture of Berge on \(\alpha\)-diperfect digraphs
• scientific article; zbMATH DE number 3891403
• Berge's conjecture and Aharoni-Hartman-Hoffman's conjecture for locally in-semicomplete digraphs
• Proof of Berge's path partition conjecture for \(k \geq \lambda - 3\)

Cites work

• scientific article; zbMATH DE number 3756511 (Why is no real title available?)
• A classification of all arc-locally semicomplete digraphs
• A classification of arc-locally semicomplete digraphs
• Critical kernel imperfect problem in generalizations of bipartite tournaments
• Digraphs. Theory, algorithms and applications
• Graph theory
• Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs
• TWO THEOREMS IN GRAPH THEORY
• The strong perfect graph theorem
• The structure of strong arc-locally in-semicomplete digraphs
• \(\alpha\)-diperfect digraphs

Cited in

(4)

• \(\alpha\)-diperfect digraphs
• BE-diperfect digraphs with stability number two
• \( \chi \)-diperfect digraphs
• 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)