-diperfect digraphs

DOI10.1016/J.DISC.2021.112759zbMATH Open1484.05088arXiv1904.02799OpenAlexW4205489416MaRDI QIDQ2113335FDOQ2113335

Maycon Sambinelli, Orlando Lee, C. Nunes da Silva

Publication date: 14 March 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $D$ be a digraph. Given a set of vertices $SsubseteqV(D)$, an $S$-path partition $mathcalP$ of $D$ is a collection of paths of $D$ such that $V(P)colonPinmathcalP$ is a partition of $V(D)$ and $|V(P)capS|=1$ for every $PinmathcalP$. We say that $D$ satisfies the $alpha$-property if, for every maximum stable set $S$ of $D$, there exists an $S$-path partition of $D$, and we say that $D$ is $alpha$-diperfect if every induced subdigraph of $D$ satisfies the $alpha$-property. A digraph $C$ is an anti-directed odd cycle if (i) the underlying graph of $C$ is a cycle $x_1{x}_{2}cdots{x}_{2k+1}{x}_1$, where $kinmathbbZ$ and $kgeq2$, and (ii) each of the vertices $x_1,x_2,x_3,x_4,x_6,$ $x_8,ldots,x_{2k}$ is either a source or a sink. Berge (1982) conjectured that a digraph is $alpha$-diperfect if, and only if, it contains no induced anti-directed odd cycle. Remark that this conjecture is strikingly similar to Berge's conjecture on perfect graphs -- nowadays known as the Strong Perfect Graph Theorem (Chudnovsky, Robertson, Seymour, and Thomas, 2006). To the best of our knowledge, Berge's conjecture for $alpha$-diperfect digraphs has been verified only for symmetric digraphs and digraphs whose underlying graph are perfect. In this paper, we verify it for digraphs whose underlying graphs are series-parallel and for in-semicomplete digraphs. Moreover, we propose a conjecture similar to Berge's and verify it for all the known cases of Berge's conjecture.

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

Recommendations

• A family of counterexamples for a conjecture of Berge on \(\alpha\)-diperfect digraphs
• Some results on Berge's conjecture and begin-end conjecture
• scientific article; zbMATH DE number 3891403
• \( \chi \)-diperfect digraphs
• The directed path partition conjecture

zbMATH Keywords

path partition\(\alpha\)-diperfect digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graph theory
• Normal hypergraphs and the perfect graph conjecture
• A classification of locally semicomplete digraphs
• Locally semicomplete digraphs: A generalization of tournaments
• Connectivity properties of locally semicomplete digraphs
• Digraphs
• The strong perfect graph theorem
• Title not available (Why is that?)
• List edge-colorings of series-parallel graphs
• Title not available (Why is that?)
• Decomposing series-parallel graphs into paths of length 3 and triangles
• A characterization of locally semicomplete CKI-digraphs
• Generalizations of tournaments: A survey
• In-tournament digraphs
• Independent sets and non-augmentable paths in generalizations of tournaments
• Longest path partitions in generalizations of tournaments
• The Merino-Welsh conjecture holds for series-parallel graphs
• On complementary cycles in locally semicomplete digraphs
• A note on spanning local tournaments in locally semicomplete digraphs
• Nonempty intersection of longest paths in series-parallel graphs
• Note on a min-max conjecture of Woodall
• Diperfect graphs
• Digraphs with the path‐merging property
• About colorings, stability and paths in directed graphs

Cited In (5)

• BE-diperfect digraphs with stability number two
• Some results on Berge's conjecture and begin-end conjecture
• Path partitions of phylogenetic networks
• A family of counterexamples for a conjecture of Berge on \(\alpha\)-diperfect digraphs
• Title not available (Why is that?)

This page was built for publication: \(\alpha\)-diperfect digraphs

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