On Greene-Kleitman's theorem for general digraphs (Q687099): Difference between revisions

Consider a directed graph \(G\) and let \(a(k,P)\) for a path \(P\) be the minimum of \(k\) and the number of vertices in \(P\). Consider a partition \(Q\) of the vertices of \(G\) into paths that minimizes the sum of \(a(k,P)\) over the blocks of \(Q\). Berge has conjectured that for any such \(Q\) there must be a coloring of some of the vertices of \(G\) in \(k\) colors, each color class being independent, such that each path \(P\) of \(Q\) meets \(a(k,P)\) of the colors. This was known to be true for acyclic graphs. In this paper a new proof of this result is given for acyclic graphs, using ideas of alternating paths; the result is also proven here for general graphs so long as \(a(k,P)=k\) for all paths \(P\) of \(Q\). These questions represent formulations and extensions of results of G. Greene and the reviewer for partially ordered sets. The dual question, answered for orders by a theorem of Greene also can be posed in the context of directed graphs, and is given as a conjecture in the paper.