Premium
On line graphs of linear 3‐uniform hypergraphs
Author(s) -
Metelsky Yury,
Tyshkevich Regina
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199708)25:4<243::aid-jgt1>3.0.co;2-k
Subject(s) - combinatorics , mathematics , vertex (graph theory) , characterization (materials science) , discrete mathematics , graph , chordal graph , intersection (aeronautics) , block graph , 1 planar graph , physics , engineering , optics , aerospace engineering
It is known that the class of line graphs of linear 3‐uniform hypergraphs cannot be characterized by a finite list of forbidden induced subgraphs (R. N. Naik, S. B. Rao, S. S. Shrikhande, and N. M. Singhi, Intersection Graphs of k ‐uniform linear hypergraphs, . (1982), 159–172). In this paper such a characterization is given provided that no vertex has degree less than 19. An analogous characterization for graphs whose vertex degrees are not less than 69 was obtained in Naik et al. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 243–251, 1997