Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514524 | Electronic Notes in Discrete Mathematics | 2005 | 8 Pages |
Abstract
Let L3l be the class of edge intersection graphs of linear 3-uniform hypergraphs. The problem of recognizing GâL3l is NP-complete. Denote by δALG the minimal integer such that the problem "GâL3l" is polynomially solvable in the class of graphs G with the minimal vertex degree δ(G)â¥Î´ALG and by δFIS the minimal integer such that L3l can be characterized by a finite list of forbidden induced subgraphs in the class of graphs G with δ(G)â¥Î´FIS. It is proved that δALGâ¤10 and δFISâ¤16.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
P.V. Skums, S.V. Suzdal, R.I. Tyshkevich,