Vertex partition problems in digraphs

• M. Sambinelli USP
• C. N. Lintzmayer UFABC
• C. N. da Silva UFSCar
• O. Lee UNICAMP

DOI: https://doi.org/10.5753/etc.2018.3174

Abstract

Let D be a digraph and k be a positive integer. Linial (1981) conjec tured that the k-norm of a k-minimum path partition of a digraph D is at most max{Σ_C∈C |C| : C is a partial k-coloring of D}. Berge (1982) conjectured that every k-minimum path partition contains a partial k-coloring orthogonal to it. It is well known that Berge’s Conjecture implies Linial’s Conjecture. In this work, we verify Berge’s Conjecture, and consequently Linial’s Conjecture, for locally in-semicomplete digraphs and k-minimum path partitions containing only two paths. Moreover, we verify a conjecture related to Berge’s and Linial’s Conjectures for locally in-semicomplete digraphs.

References

Aharoni, R. and Hartman, I. B.-A. (1993). On Greene-Kleitman’s theorem for general digraphs. Discrete Math., 120(1-3):13–24.

Aharoni, R., Hartman, I. B.-A., and Hoffman, A. J. (1985). Path partitions and packs of acyclic digraphs. Pacific J. Math., 118(2):249–259.

Bang-Jensen, J. and Gutin, G. (2009). Digraphs: Theory, algorithms and applications. Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London, 2nd edition.

Bang-Jensen, J. r., Guo, Y., Gutin, G., and Volkmann, L. (1997). A classification of locally semicomplete digraphs. Discrete Math., 167/168:101–114. 15th British Combinatorial Conference (Stirling, 1995).

Bang-Jensen, J. r., Nielsen, M. H., and Yeo, A. (2006). Longest path partitions in generalizations of tournaments. Discrete Math., 306(16):1830–1839.

Berge, C. (1982). k-optimal partitions of a directed graph. European J. Combin., 3(2):97–101.

Berge, C. (1997). Motivations and history of some of my conjectures. Discrete Math., 165/166:61–70. Graphs and combinatorics (Marseille, 1995).

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

Galeana-Sánchez, H. and Gómez, R. (2008). Independent sets and non-augmentable paths in generalizations of tournaments. Discrete Math., 308(12):2460–2472.

Gallai, T. (1968). On directed paths and circuits. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 115–118. Academic Press, New York.

Guo, Y. and Volkmann, L. (1994). Connectivity properties of locally semicomplete digraphs. J. Graph Theory, 18(3):269–280.

Hartman, I. B.-A. (2006). Berge’s conjecture on directed path partitions—a survey. Discrete Math., 306(19-20):2498–2514.

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

Herskovics, D. (2016). Proof of Berge’s path partition conjecture for k 3. Discrete Appl. Math., 209:137–143.

Linial, N. (1978). Covering digraphs by paths. Discrete Math., 23(3):257–272.

Linial, N. (1981). Extending the Greene-Kleitman theorem to directed graphs. J. Combin. Theory Ser. A, 30(3):331–334.

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