×

Berge’s conjecture and Aharoni-Hartman-Hoffman’s conjecture for locally in-semicomplete digraphs. (English) Zbl 1416.05125

Summary: Let \(k\) be a positive integer and let \(D\) be a digraph. A path partition \(\mathcal {P}\) of \(D\) is a set of vertex-disjoint paths which covers \(V(D)\). Its \(k\)-norm is defined as \(\sum _{P \in \mathcal {P}} \min \{|V(P)|, k\}\). A path partition is \(k\)-optimal if its \(k\)-norm is minimum among all path partitions of \(D\). A partial \(k\)-coloring is a collection of \(k\) disjoint stable sets. A partial \(k\)-coloring \(\mathcal {C}\) is orthogonal to a path partition \(\mathcal {P}\) if each path \(P \in \mathcal {P}\) meets \(\min \{|V(P)|,k\}\) distinct sets of \(\mathcal {C}\). C. Berge [Eur. J. Comb. 3, 97–101 (1982; Zbl 0501.05037)] conjectured that every \(k\)-optimal path partition of \(D\) has a partial \(k\)-coloring orthogonal to it. A (path) \(k\)-pack of \(D\) is a collection of at most \(k\) vertex-disjoint paths in \(D\). Its weight is the number of vertices it covers. A \(k\)-pack is optimal if its weight is maximum among all \(k\)-packs of \(D\). A coloring of \(D\) is a partition of \(V(D)\) into stable sets. A \(k\)-pack \(\mathcal {P}\) is orthogonal to a coloring \(\mathcal {C}\) if each set \(C \in \mathcal {C}\) meets \(\min \{|C|, k\}\) paths of \(\mathcal {P}\). R. Aharoni et al. [Pac. J. Math. 118, 249–259 (1985; Zbl 0569.05024)] conjectured that every optimal \(k\)-pack of \(D\) has a coloring orthogonal to it. A digraph \(D\) is semicomplete if every pair of distinct vertices of \(D\) are adjacent. A digraph \(D\) is locally in-semicomplete if, for every vertex \(v \in V(D)\), the in-neighborhood of \(v\) induces a semicomplete digraph. Locally out-semicomplete digraphs are defined similarly. In this paper, we prove Berge’s and Aharoni-Hartman-Hoffman’s conjectures for locally in/out-semicomplete digraphs.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

References:

[1] Aharoni, R., Hartman, I.B.A.: On Greene-Kleitman’s theorem for general digraphs. Discrete Math. 120(1-3), 13-24 (1993) · Zbl 0786.05037 · doi:10.1016/0012-365X(93)90561-7
[2] Aharoni, R., Hartman, I.B.A., Hoffman, A.J.: Path partitions and packs of acyclic digraphs. Pac. J. Math. 2(118), 249-259 (1985) · Zbl 0569.05024 · doi:10.2140/pjm.1985.118.249
[3] Bang-Jensen, J.: Locally semicomplete digraphs: A generalization of tournaments. J. Graph Theory 14(3), 371-390 (1990) · Zbl 0703.05026 · doi:10.1002/jgt.3190140310
[4] Bang-Jensen, J.: Digraphs with the path-merging property. J. Graph Theory 20(2), 255-265 (1995) · Zbl 0832.05047 · doi:10.1002/jgt.3190200214
[5] Bang-Jensen, J., Guo, Y., Gutin, G., Volkmann, L.: A classification of locally semicomplete digraphs. Discrete Math. 167, 101-114 (1997) · Zbl 0873.05072 · doi:10.1016/S0012-365X(96)00219-1
[6] Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer Monographs in Mathematics, Springer, London (2009) · Zbl 1170.05002 · doi:10.1007/978-1-84800-998-1
[7] Bang-Jensen, J., Nielsen, M.H., Yeo, A.: Longest path partitions in generalizations of tournaments. Discrete Math. 306(16), 1830-1839 (2006) · Zbl 1103.05036 · doi:10.1016/j.disc.2006.03.063
[8] Berge, \[C.: k\] k-optimal partitions of a directed graph. Eur. J. Comb. 3(2), 97-101 (1982) · Zbl 0501.05037 · doi:10.1016/S0195-6698(82)80022-X
[9] Berger, E., Hartman, I.B.A.: Proof of Berge’s strong path partition conjecture for \[k = 2\] k=2. Eur. J. Comb. 29(1), 179-192 (2008) · Zbl 1126.05078 · doi:10.1016/j.ejc.2006.10.003
[10] Cameron, K.: On \[k\] k-optimum dipath partitions and partial \[k\] k-colourings of acyclic digraphs. Eur. J. Comb. 7(2), 115-118 (1986) · Zbl 0603.05020 · doi:10.1016/S0195-6698(86)80036-1
[11] Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(1), 161-166 (1950) · Zbl 0038.02003 · doi:10.2307/1969503
[12] Galeana-Sánchez, H., Olsen, M.: A characterization of locally semicomplete CKI-digraphs. Graphs Comb. 32(5), 1873-1879 (2016) · Zbl 1351.05096 · doi:10.1007/s00373-016-1708-9
[13] Galeana-Sánchez, H., Gómez, R.: Independent sets and non-augmentable paths in generalizations of tournaments. Discrete Math. 308(12), 2460-2472 (2008) · Zbl 1147.05042 · doi:10.1016/j.disc.2007.05.016
[14] Gallai, T.: On directed paths and circuits. Theory Graphs 38, 115-118 (1968) · Zbl 0159.54403
[15] Gallai, T., Milgram, A.N.: Verallgemeinerung eines graphentheoretischen Satzes von Rédei. Acta Sci. Math. 21, 181-186 (1960) · Zbl 0101.16608
[16] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979) · Zbl 0411.68039
[17] Greene, C.: Some partitions associated with a partially ordered set. J. Comb. Theory Ser. A 20(1), 69-79 (1976) · Zbl 0323.06002 · doi:10.1016/0097-3165(76)90078-9
[18] Greene, C., Kleitman, D.J.: The structure of Sperner \[k\] k-families. J. Comb. Theory Ser. A 20(1), 41-68 (1976) · Zbl 0361.05016 · doi:10.1016/0097-3165(76)90077-7
[19] Guo, Y., Volkmann, L.: Connectivity properties of locally semicomplete digraphs. J. Graph Theory 18(3), 269-280 (1994a) · Zbl 0830.05043
[20] Guo, Y., Volkmann, L.: On complementary cycles in locally semicomplete digraphs. Discrete Math. 135(1), 121-127 (1994b) · Zbl 0816.05036
[21] Hartman, I.B.A., Saleh, F., Hershkowitz, D.: On Greene’s theorem for digraphs. J. Graph Theory 18(2), 169-175 (1994) · Zbl 0797.05049 · doi:10.1002/jgt.3190180208
[22] Herskovics, D.: Proof of Berge’s path partition conjecture for \[k \ge \lambda -3\] k≥λ-3. Discrete Appl. Math. 209, 137-143 (2016) (9th International Colloquium on Graph Theory and Combinatorics, 2014, Grenoble) · Zbl 1339.05311
[23] Huang, J.: A note on spanning local tournaments in locally semicomplete digraphs. Discrete Appl. Math. 89(1), 277-279 (1998) · Zbl 0919.05025 · doi:10.1016/S0166-218X(98)00113-9
[24] Linial, N.: Covering digraphs by paths. Discrete Math. 23(3), 257-272 (1978) · Zbl 0388.05038 · doi:10.1016/0012-365X(78)90007-9
[25] Linial, N.: Extending the Greene-Kleitman theorem to directed graphs. J. Comb. Theory Ser. A 30(3), 331-334 (1981) · Zbl 0467.05029 · doi:10.1016/0097-3165(81)90029-7
[26] Mirsky, L.: A dual of Dilworth’s decomposition theorem. Am. Math. Mon. 78, 876-877 (1971) · Zbl 0263.06002 · doi:10.1080/00029890.1971.11992886
[27] Roy, B.: Nombre chromatique et plus longs chemins d’un graphe. Rev. Française d’informatique et de Recherche Opérationnelle 1(5), 129-132 (1967) · Zbl 0157.31302 · doi:10.1051/m2an/1967010501291
[28] Sridharan, S.: On the strong path partition conjecture of Berge. Discrete Math. 117(1-3), 265-270 (1993) · Zbl 0783.05067 · doi:10.1016/0012-365X(93)90341-P
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.