Linial's Conjecture for Arc-spine Digraphs
Lucas Rigo Yoshimura, Maycon Sambinelli, Cândida N. da Silva, Orlando Lee · Electronic Notes in Theoretical Computer Science · 2019
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 min { | P i | , 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.