FINDING REGULAR SUBGRAPHS IN BOTH ARBITRARY AND PLANAR GRAPHS

Authors
STEWART IA
Citation
Ia. Stewart, FINDING REGULAR SUBGRAPHS IN BOTH ARBITRARY AND PLANAR GRAPHS, Discrete applied mathematics, 68(3), 1996, pp. 223-235
Citations number
9
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
68
Issue
3
Year of publication
1996
Pages
223 - 235
Database
ISI
SICI code
Abstract
We show that the problems of deciding (i) whether an arbitrary graph h as a k-regular subgraph, for some given k greater than or equal to 3, (ii) whether a planar graph has a quartic subgraph, and (iii) whether a planar graph has a quintic subgraph, are complete for NP via logspac e reductions. There are no regular planar graphs of degree greater tha n 5.