Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Texto completo
Autor(es):
Sambinelli, Maycon [1] ; Lintzmayer, Carla Negri [2] ; da Silva, Candida Nunes [3] ; Lee, Orlando [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[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
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: GRAPHS AND COMBINATORICS; v. 35, n. 4, p. 921-931, JUL 2019.
Citações Web of Science: 0
Resumo

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)

Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 16/14132-4 - Empacotamentos uni e bidimensionais com restrições de conflitos e remoções
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Brasil - Pós-Doutorado