Representation theorems for graphs whose vertex set is partially ordered
type: Item
instance of: scholarly article
title: Representation theorems for graphs whose vertex set is partially ordered
zbMATH Open document ID: 0557.05056
DOI: 10.1016/0012-365X(85)90143-8
author: Alain Quilliot
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 3887744
zbMATH Keywords: partial order
zbMATH Keywords: graphs
zbMATH Keywords: hypergraph
zbMATH Keywords: interval graphs
zbMATH Keywords: circular graphs
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: Q5570136
cites work: Q5615282
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Structure theorems for some circular-arc graphs
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
cites work: Q4138414
cites work: Q4200096
description: scientific article; zbMATH DE number 3887744