Path partitions and packs of acyclic digraphs (Q1061135)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Path partitions and packs of acyclic digraphs |
scientific article |
Statements
Path partitions and packs of acyclic digraphs (English)
0 references
1985
0 references
The authors raise the following conjecture: Let G be a directed graph and let k be a positive integer. Then for every family \(\{P_ 1,P_ 2,...,P_ t\}\) of at most k disjoint paths for which \(| \cup^{t}_{i=1}V(P_ i)|\) is as large as possible, there exists a coloring \(\{C_ 1,C_ 2,...,C_ m\}\) such that every color class \(C_ i\) meets \(\min \{| C_ i|,k\}\) different paths of \(\{P_ i\}\). They prove that the conjecture holds for any acyclic digraph. The above mentioned conjecture is, in a sense, dual to a conjecture by Berge.
0 references
path partition
0 references
acyclic digraph
0 references