On the problem of how to represent a graph taking into account an additional structure
type: Item
instance of: scholarly article
title: On the problem of how to represent a graph taking into account an additional structure
zbMATH Open document ID: 0643.05053
DOI: 10.1016/0095-8956(88)90092-5
author: Alain Quilliot
published in: Journal of Combinatorial Theory. Series B
publication date: 1988-01-01T00:00:00Z
review text: A finite undirected graph \(G=(X,E)\) is given such that every non isolated vertex is provided with a loop. In this note is tried to express such a graph as the intersection graph of a finite hypergraph H(Y,F) by using a suitable inclusion relation between every edge and every union of edges in H. In a first problem given G and an order \(\leq\) on X and it is wanted to find an hypergraph H and a surjective function from X to F satisfying given conditions. If it is possible to find such an H, then G is called \(\leq\)-representable. In Theorem 1 is proved the equivalence between \(\leq\)-representation of G and satisfying two conditions. In a second problem is given a relation R between the elements of X and the subsets of X and it is wanted to find an hypergraph H and a surjective function from X to F satisfying two given conditions. If we can find such an H, then G is called R-representable. In Theorem 2 is proved the equivalence between R-representation of G and satisfying four conditions. This proof is a very extensive one, many lemmata and numerous distinctions of cases are necessary. Then two consequences of Theorem 2 follow: first in the case that R is a relation used in the first problem and by considering strong \(<\)-representation. In Theorem 3 a further problem with respect to a so-called U-covered graph is researched. Finally in this note are given some examples: - In Theorem 4 is proved that G is an interval graph if and only if three certain conditions are satisfied. - A necessary condition for a graph to be a circular arcgraph is deduced.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4047775
zbMATH Keywords: hypergraph
zbMATH Keywords: representation
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: 0095-8956(88)90092-5
OpenAlex ID: W2987430707
cites work: Q5570136
cites work: Q5615282
cites work: Transitiv orientierbare Graphen
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Q4138414
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
cites work: Structure theorems for some circular-arc graphs
description: scientific article; zbMATH DE number 4047775