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. |