Linial's Conjecture for Arc-spine Digraphs

Autor(es)

Yoshimura, Lucas R. ; Sambinelli, Maycon ; da Silva, Candida N. ; Lee, Orlando

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 12-pg., 2019-08-30.

Resumo

A path partition P of a digraph D is a collection of directed paths such that every vertex belongs to precisely one path. Given a positive integer k, the k-norm of a path partition P of D is defined as Sigma(P is an element of P) min{vertical bar P-i vertical bar, k}. A path partition of a minimum k-norm is called k-optimal and its k-norm is denoted by pi(k) (D). A stable set of a digraph D is a subset of pairwise non-adjacent vertices of V(D). Given a positive integer k, we denote by alpha(k)(D) the largest set of vertices of D that can be decomposed into k disjoint stable sets of D. In 1981, Linial conjectured that pi(k) (D) <= alpha(k) (D) for every digraph. We say that a digraph D is arc-spine if V(D) can be partitioned into two sets X and Y where X is traceable and Y contains at most one arc in A(D). In this paper we show the validity of Linial's Conjecture for arc-spine digraphs. (AU)

• Processo FAPESP: 17/21345-7 - Partição em caminhos e conjuntos independentes em digrafos
• Beneficiário: Lucas Rigo Yoshimura
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Processo FAPESP: 17/23623-4 - Problemas de partição em grafos e dígrafos
• Beneficiário: Maycon Sambinelli
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• 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
• Modalidade de apoio: Auxílio à Pesquisa - Temático