Representation theorems for graphs whose vertex set is partially ordered (Q762181)

In the paper graphs with partially ordered vertex sets are studied. Three main problems are considered. The first problem concerns the \(<\)- representability. A graph \(G=(X,E)\) with the order relation \(<\) on X is \(<\)-representable, if there exists a hypergraph \(H=(Y,F)\) and a surjection \(p:X\to F\) such that two vertices x, y are adjacent in G if and only if \(p(x)\cap p(y)\neq \emptyset\) and \(x\leq y\) if and only if \(p(x)\subset p(y).\) The second problem concerns the strong \(<\)- representability which is a strengthening of the \(<\)-representability (p is defined on the set of all subsets of X). The third problem concerns the U-covering. Here \(G=(X,E)\) is a graph and U is a non-empty family of subsets of X with the property that \(A\in U\), \(A\subset B\subset X\) implies \(B\in U\). The graph G is U-covered, if there exists a hypergraph \(H=(Y,F)\) and a surjection \(p:X\to F\) such that x, y are adjacent in G if and only if \(p(x)\cap p(y)\neq \emptyset\) and \(A\in U\) if and only if \(\cup_{x\in A}p(x)=Y.\) The characterization theorems for the described properties are proved. At the end the applications to interval graphs and circular graphs are shown.