首页 | 本学科首页   官方微博 | 高级检索  
     


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 View the MathML source be the class of edge intersection graphs of linear 3-uniform hypergraphs. It is known that the problem of recognition of the class View the MathML source 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 View the MathML source 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号