Path partitions and packs of acyclic digraphs (Q1061135): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2078959432 / rank | |||
Normal rank |
Latest revision as of 01:30, 20 March 2024
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