Some Results on Berge's Conjecture and Begin-End Conjecture

Autor(es)

Freitas, Lucas Ismaily Bezerra ; Lee, Orlando

• Tipo de documento: Artigo Científico
• Fonte: GRAPHS AND COMBINATORICS; v. 38, n. 4, p. 23-pg., 2022-08-01.

Resumo

Let D be a digraph. A subset S of V(D) is stable if every pair of vertices in S is non-adjacent in D. A collection of disjoint paths P of D is a path partition of V(D), if every vertex in V(D) is on a path of P. We say that a stable set S and a path partition P are orthogonal if every 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 is a path partition P orthogonal to S. A digraph D is alpha-diperfect if every induced subdigraph of D satisfies the alpha-property. In 1982, 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 is a path partition P such that (i) S and P are orthogonal and (ii) for each path P is an element of P, either the initial or the final 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, it follows that alpha(D)<vertical bar V(D)vertical bar/2. Moreover, we prove both conjectures for arc-locally (out) in-semicomplete digraphs. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático