|
|||||
|
|
On Greene-Kleitman's theorem for general digraphs |
|
| Authors: | Ron Aharoni Irith Ben-Arroyo Hartman |
| Institution: | Mathematics Department, Technion-Israel Institute of Technology, Haifa 32000, Israel IBM Israel-Science and Technology, Technion City, Haifa 32000, Israel |
| Abstract: | Linial conjectured that Greene—Kleitman's theorem can be extended to general digraphs. We prove a stronger conjecture of Berge for digraphs having k-optimal path partitions consisting of ‘long’ paths. The same method yields known results for acyclic digraphs, and extensions of various theorems of Greene and Frank to acyclic digraphs. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |