Recognizing intersection graphs of linear uniform hypergraphs
type: Item
instance of: scholarly article
title: Recognizing intersection graphs of linear uniform hypergraphs
zbMATH Open document ID: 0895.05046
DOI: 10.1007/BF03353014
author: Michael Jacobson
author: André E. Kézdy
author: Jeno Lehel
published in: Graphs and Combinatorics
publication date: 1998-09-06T00:00:00Z
review text: Let \(H =(V,E)\) be a hypergraph with vertex set \(V\) and edge set \(E\). If two distinct hyperedges of \(H\) share one common vertex, they define an edge of the intersection graph of \(H\), where \(E\) is taken as its vertex set. A hypergraph is linear if any two distinct hyperedges have at most one common vertex. The authors show the existence of a polynomial algorithm for deciding whether a graph of minimum degree \( \delta \geq 19\) is the intersection graph of a linear 3-uniform hypergraph. This improves some result in \textit{R. N. Naik, S. B. Rao, S. S. Shrikhande}, and \textit{N. M. Singhi} [Eur. J. Comb. 3, 159-172 (1982; Zbl 0491.05046)].
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1106814
zbMATH Keywords: hypergraph
zbMATH Keywords: intersection graph
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: \(k\)-uniform hypergraph
zbMATH Keywords: linear hypergraph
reviewed by: Toru Ishihara
MaRDI profile type: Publication
cites work: Q5570136
cites work: Q5668821
cites work: Q3993087
cites work: Line graphs of hypergraphs. I
cites work: Q3861439
cites work: Q4393240
cites work: Q4378523
cites work: Intersection graphs of k-uniform linear hypergraphs
cites work: A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
cites work: The interchange graph of a finite graph
description: scientific article; zbMATH DE number 1106814