Article ID Journal Published Year Pages File Type
9514524 Electronic Notes in Discrete Mathematics 2005 8 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,