TY - JOUR
AU - Cruz, Jadder Bismarck de Sousa
AU - Silva, Cândida Nunes da
AU - Lee, Orlando
PY - 2021
TI - Some Partial Results on Linial's Conjecture for Matching-Spine Digraphs
JF - Anais do Encontro de Teoria da Computação (ETC); 2021: Anais do VI Encontro de Teoria da Computação
DO - 10.5753/etc.2021.16386
KW -
N2 - Let $k$ be a positive integer. A \emph{partial $k$-coloring} of a digraph $D$ is a set $\calC$ of $k$ disjoint stable sets and has \emph{weight} defined as $\sum_{C \in \calC} |C|$. An \emph{optimal} $k$-coloring is a $k$-coloring of maximum weight. A \emph{path partition} of a digraph $D$ is a set $\calP$ of disjoint paths of $D$ that covers its vertex set and has \emph{$k$-norm} defined as $\sum_{P \in \mathcal{P}} \min\{|P|,k\}$. A path partition $\calP$ is \emph{$k$-optimal} if it has minimum $k$-norm. A digraph $D$ is \emph{matching-spine} if its vertex set can be partitioned into sets $X$ and $Y$, such that $D[X]$ has a Hamilton path and the arc set of $D[Y]$ is a matching. Linial (1981) conjectured that the $k$-norm of a $k$-optimal path partition of a digraph is at most the weight of an optimal partial $k$-coloring. We present some partial results on this conjecture for matching-spine digraphs.
UR - https://sol.sbc.org.br/index.php/etc/article/view/16386