Linial's Dual Conjecture for Path-Spine Digraphs
Resumo
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.
Referências
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.
