ON GREENES THEOREM FOR DIGRAPHS

Greene's Theorem states that the maximum cardinality of an optimal k-p ath 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 fog general digraphs in which an optimal k-path contains a path of cardinality one. This i mplies the validity of the conjecture for all bipartite digraphs. We a lso extend Greene's Theorem to all split graphs. (C) 1994 John Wiley & Sons, Inc.