Bound graph polysemy (Q1574662)

Given a poset \(P\), the Hasse diagram and the comparability graph are examples of graphs whose properties naturally reflect properties of \(P\). Conversely, given a graph \((V,E)= G\) it may be possible to order \(V\) as \(P= (V,\leq)\) so as to reflect properties of \(G\) in those of \(P\). Thus an upper (lower) bound graph \(G\) is one for which adjacency in \(G\) may be replaced by existence of an upper (lower) bound in \(G\). Bound polysemy is the property of any pair \((G_1,G_2)\) of graphs on a shared vertex set \(V\) for which there exists a partial order \(P= (V,\leq)\) such that any pair of vertices has an upper bound precisely when it is an edge of \(G_1\) and a lower bound precisely when it is an edge in \(G_2\). By passing through a common poset \(P\), it is reasonable to assume that \(G_1\) and \(G_2\) should have properties which are somewhat ``dual'' and which ought to be recognizable. In this paper the study of this notion is continued from earlier researches and in particular it is observed (Theorem 16) that if \(G_1= (V,E_1)\) and \(G_2= (V,E_2)\) are associated with a bipartite \(P\), then \(G_3= (V,E_1\cup E_2)\) is a squared graph with square root the Hasse diagram of \(P\), among other results of interest.