Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
Sambinelli, Maycon [1] ; Lintzmayer, Carla Negri [2] ; da Silva, Candida Nunes [3] ; Lee, Orlando [1]
Total Authors: 4
Affiliation:
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Fed Univ ABC, Ctr Math Comp & Cognit, Santo Andre, SP - Brazil
[3] Univ Fed Sao Carlos, Dept Comp, Sorocaba, SP - Brazil
Total Affiliations: 3
Document type: Journal article
Source: GRAPHS AND COMBINATORICS; v. 35, n. 4, p. 921-931, JUL 2019.
Web of Science Citations: 0
Abstract

Let k be a positive integer and let D be a digraph. A path partitionP of D is a set of vertex-disjoint paths which coversV(D). Its k-norm is defined as Sigma PPmin[|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 C is orthogonal to a path partition P if each path PP meets min[|V(P)|,k] distinct sets of 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 P is orthogonal to a coloring C if each set CC meets min[|C|,k] paths of 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 vV(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. (AU)

FAPESP's process: 16/14132-4 - One and two-dimensional bin packing with conflicts and unloading restrictions
Grantee:Carla Negri Lintzmayer
Support type: Scholarships in Brazil - Post-Doctorate
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support type: Research Projects - Thematic Grants