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

DOI10.1007/S00373-019-02046-XzbMATH Open1416.05125arXiv1708.06691OpenAlexW2962791368WikidataQ123274498 ScholiaQ123274498MaRDI QIDQ2000583FDOQ2000583

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

Publication date: 28 June 2019

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

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.

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)

Cites Work

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

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)