Strict refinement for graphs and digraphs (Q1072575)

We show that any two cartesian factorizations of a connected graph have a strict common refinement, improving on the unique factorization theorem of G. Sabidussi. (The cartesian product is the product wherein two vertices are adjacent when they are adjacent in one coordinate and equal in all other coordinates.) Among the applications, we can deduce the strict refinement theorem for chain-finite posets, and (using a cartesian factorization algorithm of P. Winkler) we give polynomial-time algorithm for cardinal factorization of connected finite posets.