Linial's Conjecture for Arc-spine Digraphs

Author(s)

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

• Document type: Journal article
• Source: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 12-pg., 2019-08-30.

Abstract

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)

• FAPESP's process: 17/21345-7 - Path partitions and stable sets in digraphs
• Grantee: Lucas Rigo Yoshimura
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• FAPESP's process: 17/23623-4 - Partition problems in graphs and digraphs
• Grantee: Maycon Sambinelli
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants