The solution of two problems on bound polysemy

A pair of graphs (G1,G2) on the same set of vertices V is called bound polysemic, if there is a poset P=(V,⩽) such that for all u,v∈V with u≠v, uv is an edge of G1 if and only if there is some w∈V such that u⩽w and v⩽w and uv is an edge of G2 if and only if there is some w∈V such that w⩽u and w⩽v. Solving two problems posed by Tanenbaum (Electron. J. Comb. 7 (2000) R43), we characterize the bound polysemic pairs for which the poset P is unique and we describe an algorithm to recognize bound polysemic pairs in O(|V|3) time.