Berge’s Conjecture and Aharoni–Hartman–Hoffman’s Conjecture for Locally In-Semicomplete Digraphs

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

Indexed on: 22 May '19Published on: 22 May '19Published in: Graphs and Combinatorics


Let k be a positive integer and let D be a digraph. A path partition \(\mathcal {P}\) of D is a set of vertex-disjoint paths which covers V(D). Its k-norm is defined as \(\sum _{P \in \mathcal {P}} \min \{|V(P)|, k\}\). A path partition is k-optimal if its k-norm is minimum among all path partitions of D. A partialk-coloring is a collection of k disjoint stable sets. A partial k-coloring \(\mathcal {C}\) is orthogonal to a path partition \(\mathcal {P}\) if each path \(P \in \mathcal {P}\) meets \(\min \{|V(P)|,k\}\) distinct sets of \(\mathcal {C}\). Berge (Eur J Comb 3(2):97–101, 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 \(\mathcal {P}\) is orthogonal to a coloring \(\mathcal {C}\) if each set \(C \in \mathcal {C}\) meets \(\min \{|C|, k\}\) paths of \(\mathcal {P}\). Aharoni et al. (Pac J Math 2(118):249–259, 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 are adjacent. A digraph D is locally in-semicomplete if, for every vertex \(v \in V(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.