Representation theorems for graphs whose vertex set is partially ordered (Q762181): Difference between revisions

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.