Some Partial Results on Linial's Conjecture for Matching-Spine Digraphs

Resumo


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.

Palavras-chave: Graph, Coloring, Path Partition, Linial' Conjecture

Referências

Berge, C. (1982). k-Optimal partitions of a directed graph. European Journal of Combinatorics, 3(2):97–101.

Berger, E. and Hartman, I. (2008). Proof of Berge’s strong path partition conjecture for k = 2. European Journal of Combinatorics, 29(1):179–192.

Dilworth, R. (1950). A decomposition theorem for partially ordered sets. Annals of Mathematics, pages 161–166.

Gallai, T. and Milgram, A. (1960). Verallgemeinerung eines graphentheoretischen satzes von Rédei. Acta Sc. Math, 21:181–186.

Greene, C. and Kleitman, D. (1976). The structure of Sperner k-families. Journal of Combinatorial Theory, Series A, 20(1):41–68.

Linial, N. (1981). Extending the Greene-Kleitman theorem to directed graphs. Journal of Combinatorial Theory, Series A, 30(3):331–334.

Sambinelli, M., Nunes da Silva, C., and Lee, O. (2017). On Linial’s conjecture for spine digraphs. Discrete Mathematics, 340(5):851–854.

Yoshimura, L., Sambinelli, M., Nunes da Silva, C., and Lee, O. (2019). Linial’s conjecture for arc-spine digraphs. Electronic Notes in Theoretical Computer Science, 346:735–746.
Publicado
18/07/2021
CRUZ, Jadder Bismarck de Sousa; SILVA, Cândida Nunes da; LEE, Orlando. Some Partial Results on Linial's Conjecture for Matching-Spine Digraphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 6. , 2021, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2021 . p. 82-85. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2021.16386.