An Extension of the Greene and Greene-Kleitman Theorems to all Digraphs
Irith Ben‐Arroyo Hartman, Benjamin de Rothschild · 2002
Let G be a directed graph, and k a positive integer. We prove that there exists a k- colouring that is orthogonal to every k-optimal partition of V(G) into paths and cycles. This extends the Greene-Kleitman Theorem to all digraphs, and relates to Berge's conjecture on path partitions and k-colourings. We also show that there exists a colouring that is orthogonal to every optimal collection of k disjoint paths and an arbitrary number of cycles, thus extending Greene's Theorem to all digraphs. We conclude with some conjectures. 1.