Competition polysemy

Following a suggestion of Tanenbaum (Electron. J. Combin. 7 (2000) R43) we introduce the notion of competition polysemic pairs of graphs. A pair of (simple) graphs (G1,G2) on the same set of vertices V is called competition polysemic, if there exists a digraph D=(V,A) 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 uw→∈A and vw→∈A and uv is an edge of G2 if and only if there is some w∈V such that wu→∈A and wv→∈A. Our main results are a characterization of competition polysemic pairs (G1,G2) in terms of edge clique covers of G1 and G2 and a characterization of the connected graphs G for which there exists a tree T such that (G,T) is competition polysemic.