Linial’s Conjecture for Arc-spine Digraphs

  • Lucas Rigo Yoshimura
  • Maycon Sambinelli
  • Cândida Nunes da Silva
  • Orlando Lee


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 P P ∈P min{|Pi |, k}. A path partition of a minimum k-norm is called k-optimal and its k-norm is denoted by π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 α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 πk(D) ≤ α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.

Palavras-chave: digraphs; path partition; Linial's Conjecture
Como Citar

Selecione um Formato
YOSHIMURA, Lucas Rigo; SAMBINELLI, Maycon; DA SILVA, Cândida Nunes; LEE, Orlando. Linial’s Conjecture for Arc-spine Digraphs. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 38. , 2019, Belém. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 .