-diperfect digraphs

DOI10.1016/J.DISC.2021.112759MaRDI QIDQ2113335zbMATH OpenOpenAlexFDO

Authors Maycon Sambinelli, C. Nunes da Silva, Orlando Lee

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(6)

• \( \chi \)-diperfect digraphs
• Path partitions of phylogenetic networks
• A family of counterexamples for a conjecture of Berge on \(\alpha\)-diperfect digraphs
• BE-diperfect digraphs with stability number two
• Some results on Berge's conjecture and begin-end conjecture
• scientific article; zbMATH DE number 3891403 (Why is no real title available?)

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)