Representation theorems for graphs whose the vertex set is partially ordered

✍ Scribed by Alain Quilliot

• Publisher: Elsevier Science
• Year: 1985
• Tongue: English
• Weight: 768 KB
• Volume: 53
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(85)90143-8

✦ Synopsis

Dedicated to E. Corominas

Given a graph G =(X, E), we try to know when it is possible to consider G as the intersection graph of a finite hypergraph, when some restrietions are given on the inclusion order induced on the edge set of this hypergraph.

We give some examples concerning the interval graphs and the circular graphs.

Nous traitons ici du probl~me qui consiste ~ trouver un hypergraphe dont le graphe d'intersection est un graphe donnt, et dont la relation d'inelusion pour les ar~tes est compatible avec une information additionnelle fournie en m~me temps que le graphe. Nous travaillons sur trois cas: Ouand le graphe a son ensemble de sommet partiellement ordonnt; Quand c'est l'ensemble des parties de l'ensemble des sommets du graphe qui est partiellement ordonnt; Et quand un filtre est donn6 sur l'ensemble des sommets du graphe pour representer les collections d'ar~tes de l'hypergraphe qui vont contenir tout les sommets de l'hypergraphe.

Nous donnons enfm quelques exemples d'applications concernant les graphes d'intervalles et les graphes circulaires.