On greene's theorem for digraphs
Irith Ben‐Arroyo Hartman, Fathi Saleh, Daniel Hershkowitz · Journal of Graph Theory · 1994
Abstract Greene's Theorem states that the maximum cardinality of an optimal k‐path in a poset is equal to the minimum k‐norm of a k‐optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general digraphs in which an optimal k‐path contains a path of cardinality one. This implies the validity of the conjecture for all bipartite digraphs. We also extend Greene's Theorem to all split graphs.