Linial's Dual Conjecture for Path-Spine Digraphs


 Given a digraph D, a coloring 𝒞 of D is a partition of V(D) into stable sets. The k-norm of 𝒞 is defined as ΣC∈𝒞 min{|C|, k}. A coloring of D with minimum k-norm has its k-norm noted by χk(D). A (path)-k-pack of a digraph D is a set of k vertex-disjoint (directed) paths of D. The weight of a k-pack is the number of vertices covered by the k-pack. We denote by λk(D) the weight of a maximum k-pack. Linial conjectured that χk(D) ≤ λk(D) for every digraph. Such conjecture remains open, but has been proved for some classes of digraphs. We prove the conjecture for path-spine digraphs, defined as follows. A digraph D is path-spine if there exists a partition {X, Y} of V(D) such that D[X] has a Hamilton path and every arc in D[Y] belongs to a single path Q. 

Palavras-chave: digraph, coloring, k-pack, Linial's Dual conjecture, spine, arc-spine, path-spine


Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Springer.

Gallai, T. (1968). On directed paths and circuits. Theory of graphs, pages 115–118. Greene, C. (1976). Some partitions associated with a partially ordered set. Journal of Combinatorial Theory, Series A, 20(1):69–79.

Hartman, I. B.-A., Saleh, F., and Hershkowitz, D. (1994). On greene’s theorem for digraphs. Journal of Graph Theory, 18(2):169–175.

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

Mirsky, L. (1971). A dual of Dilworth’s decomposition theorem. Amer. Math. Monthly, 78:876–877.

Roy, B. (1967). Nombre chromatique et plus longs chemins d’un graphe. ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 1(5):129–132.

Sambinelli, M. (2018). Problemas de partição em grafos e digrafos. PhD thesis, Universidade Estadual de Campinas.

Sambinelli, M., da Silva, C. N., and Lee, O. (2017a). Advances in Aharoni-Hartman-Hoffman’s conjecture for split digraphs. Electronic Notes in Discrete Mathematics, 62:111 – 116. Proceedings of LAGOS’17.

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

Sambinelli, M., Negri Lintzmayer, C., Nunes Da Silva, C., and Lee, O. (2019). Berge’s conjecture and Aharoni—Hartman—Hoffman’s conjecture for locally in-semicomplete digraphs. Graph. Comb., 35(4):921–931.

Yoshimura, L. R., Sambinelli, M., da Silva, C. N., and Lee, O. (2019). Linial’s conjecture for arc-spine digraphs. Electronic Notes in Theoretical Computer Science, 346:735–746.
Como Citar

Selecione um Formato
CARVALHO, Vinícius de Souza; DA SILVA, Cândida Nunes; LEE, Orlando. Linial's Dual Conjecture for Path-Spine Digraphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 93-96. ISSN 2595-6116. DOI: