# 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 '19**Published on: **22 May '19**Published in: **Graphs and Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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.