On Linial’s Conjecture for Split Digraphs
Resumo
In this paper we show that Linial’s Conjecture holds for two classes of split digraphs, namely the spider digraphs and the k-loose digraphs.
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. B.-A. (2008). Proof of Berge’s strong path partition conjecture for k = 2. European Journal of Combinatorics, 29(1):179–192.
Dilworth, R. P. (1950). A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161–166.
Gallai, T. and Milgram, A. N. (1960). Verallgemeinerung eines graphentheoretischen satzes von r´edei. Acta Sci Math, 21:181–186.
Greene, C. and Kleitman, D. J. (1976). The structure of Sperner k-families. Journal of Combinatorial Theory, Series
A, 20(1):41–68.
Herskovics, D. (2013). Proof of Berge’s path partition conjecture for k − 3. Technical Report TR-2013-08,
Egerv´ary Research Group, Budapest.
Ho`ang, C. T. (1985). Perfect Graphs. PhD thesis, School of Computer Science, McGill University Montreal.
Linial, N. (1978). Covering digraphs by paths. Discrete Mathematics, 23(3):257–272.
Linial, N. (1981). Extending the Greene-Kleitman theorem to directed graphs. Journal of Combinatorial Theory, Series A, 30(3):331–334.
R´edei, L. (1934). Ein kombinatorischer satz. Acta Litt. Szeged, 7(39-43):97.
Saks, M. (1979). A short proof of the existence of k-saturated partitions of partially ordered sets. Advances in Mathematics, 33(3):207–211.
Berger, E. and Hartman, I. B.-A. (2008). Proof of Berge’s strong path partition conjecture for k = 2. European Journal of Combinatorics, 29(1):179–192.
Dilworth, R. P. (1950). A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161–166.
Gallai, T. and Milgram, A. N. (1960). Verallgemeinerung eines graphentheoretischen satzes von r´edei. Acta Sci Math, 21:181–186.
Greene, C. and Kleitman, D. J. (1976). The structure of Sperner k-families. Journal of Combinatorial Theory, Series
A, 20(1):41–68.
Herskovics, D. (2013). Proof of Berge’s path partition conjecture for k − 3. Technical Report TR-2013-08,
Egerv´ary Research Group, Budapest.
Ho`ang, C. T. (1985). Perfect Graphs. PhD thesis, School of Computer Science, McGill University Montreal.
Linial, N. (1978). Covering digraphs by paths. Discrete Mathematics, 23(3):257–272.
Linial, N. (1981). Extending the Greene-Kleitman theorem to directed graphs. Journal of Combinatorial Theory, Series A, 30(3):331–334.
R´edei, L. (1934). Ein kombinatorischer satz. Acta Litt. Szeged, 7(39-43):97.
Saks, M. (1979). A short proof of the existence of k-saturated partitions of partially ordered sets. Advances in Mathematics, 33(3):207–211.
Publicado
04/07/2016
Como Citar
SAMBINELLI, Maycon; DA SILVA, Cândida Nunes; LEE, Orlando.
On Linial’s Conjecture for Split Digraphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 776-779.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9748.
