Edge intersection graphs of linear 3-uniform hypergraphs |
| |
Authors: | P.V. Skums S.V. Suzdal |
| |
Affiliation: | Mechanics and Mathematics Faculty, Belarus State University, Minsk, Belarus |
| |
Abstract: | Let be the class of edge intersection graphs of linear 3-uniform hypergraphs. It is known that the problem of recognition of the class is NP-complete. We prove that this problem is polynomially solvable in the class of graphs with minimum vertex degree ≥10. It is also proved that the class is characterized by a finite list of forbidden induced subgraphs in the class of graphs with minimum vertex degree ≥16. |
| |
Keywords: | Edge intersection graph Linear 3-uniform hypergraph Forbidden induced subgraph Krausz decomposition |
本文献已被 ScienceDirect 等数据库收录! |