DECIDING WHETHER A PLANAR GRAPH HAS A CUBIC SUBGRAPH IS NP-COMPLETE

被引：11

作者：

STEWART, IA ^{[1
]}

机构：

[1] UNIV NEWCASTLE UPON TYNE,COMP LAB,NEWCASTLE TYNE NE1 7RU,TYNE & WEAR,ENGLAND

来源：

DISCRETE MATHEMATICS | 1994年 / 126卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(94)90277-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the problem of deciding whether a given planar graph (complete with planar embedding) of degree at most 7 has a cubic subgraph is NP-complete.

引用

页码：349 / 357

页数：9