Even and odd pairs in comparability and in P4-comparability graphs

We characterize even and odd pairs in comparability and in P4-comparability graphs. The characterizations lead to simple algorithms for deciding whether a given pair of vertices forms an even or odd pair in these classes of graphs. The complexities of the proposed algorithms are O(n + m) for comparability graphs and O(n²m) for P4-comparability graphs. The former represents an improvement over a recent algorithm of complexity O(nm).