Berge's conjecture and Aharoni-Hartman-Hoffman's conjecture for locally in-semicomplete digraphs

DOI10.1007/S00373-019-02046-XMaRDI QIDQ2000583zbMATH OpenOpenAlexWikidataFDO

Authors Maycon Sambinelli, Carla Negri Lintzmayer, Cândida Nunes da Silva, Orlando Lee

Publication date 28 June 2019

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

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

zbMATH Keywords

Aharoni-Hartman-Hoffman's conjecturelocally in-semicomplete digraphs

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 $k$ be a positive integer and let $D$ be a digraph. A path partition $sP$ of $D$ is a set of vertex-disjoint paths which covers $V(D)$. Its $k$-norm is defined as $su{m}_{PinsP}Min|V(P)|,k$. A path partition is $k$-optimal if its $k$-norm is minimum among all path partitions of $D$. A partial $k$-coloring is a collection of $k$ disjoint stable sets. A partial $k$-coloring $sC$ is orthogonal to a path partition $sP$ if each path $PinsP$ meets $min|P|,k$ distinct sets of $sC$. Berge (1982) conjectured that every $k$-optimal path partition of $D$ has a partial $k$-coloring orthogonal to it. A (path) $k$-pack of $D$ is a collection of at most $k$ vertex-disjoint paths in $D$. Its weight is the number of vertices it covers. A $k$-pack is optimal if its weight is maximum among all $k$-packs of $D$. A coloring of $D$ is a partition of $V(D)$ into stable sets. A $k$-pack $sP$ is orthogonal to a coloring $sC$ if each set $CinsC$ meets $Min|C|,k$ paths of $sP$. Aharoni, Hartman and Hoffman (1985) conjectured that every optimal $k$-pack of $D$ has a coloring orthogonal to it. A digraph $D$ is semicomplete if every pair of distinct vertices of $D$ is adjacent. A digraph $D$ is locally in-semicomplete if, for every vertex $vinV(D)$, the in-neighborhood of $v$ induces a semicomplete digraph. Locally out-semicomplete digraphs are defined similarly. In this paper, we prove Berge's and Aharoni-Hartman-Hoffman's Conjectures for locally in/out-semicomplete digraphs.

Recommendations

• Proof of Berge's path partition conjecture for \(k \geq \lambda - 3\)
• Advances in Aharoni-Hartman-Hoffman's conjecture for split digraphs
• On the Berge's strong path partition conjecture
• On the strong path partition conjecture of Berge
• Path partitions and packs of acyclic digraphs

Cites work

• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• A Dual of Dilworth's Decomposition Theorem
• A characterization of locally semicomplete CKI-digraphs
• A classification of locally semicomplete digraphs
• A decomposition theorem for partially ordered sets
• A note on spanning local tournaments in locally semicomplete digraphs
• Connectivity properties of locally semicomplete digraphs
• Covering digraphs by paths
• Digraphs
• Digraphs with the path‐merging property
• Extending the Greene-Kleitman theorem to directed graphs
• Independent sets and non-augmentable paths in generalizations of tournaments
• Locally semicomplete digraphs: A generalization of tournaments
• Longest path partitions in generalizations of tournaments
• Nombre chromatique et plus longs chemins d'un graphe
• On Greene-Kleitman's theorem for general digraphs
• On complementary cycles in locally semicomplete digraphs
• On greene's theorem for digraphs
• On k-optimum dipath partitions and partial k-colourings of acyclic digraphs
• On the strong path partition conjecture of Berge
• Path partitions and packs of acyclic digraphs
• Proof of Berge's path partition conjecture for \(k \geq \lambda - 3\)
• Proof of Berge's strong path partition conjecture for \(k=2\)
• Some partitions associated with a partially ordered set
• The structure of Sperner k-families
• k-optimal partitions of a directed graph

Cited in

(3)

• On Linial's conjecture for spine digraphs
• Some results on Berge's conjecture and begin-end conjecture
• Proof of Berge's path partition conjecture for \(k \geq \lambda - 3\)

This page was built for publication: Berge's conjecture and Aharoni-Hartman-Hoffman's conjecture for locally in-semicomplete digraphs

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