Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!cs.utexas.edu!tut.cis.ohio-state.edu!purdue!dey
From: dey@cs.purdue.EDU (Tamal Krishna Dey)
Newsgroups: comp.theory
Subject: minimum vertex-cover for 3-connected planar graphs
Keywords: vertex-cover, NP-completeness
Message-ID: <8627@medusa.cs.purdue.edu>
Date: 13 Nov 89 16:58:11 GMT
Sender: news@cs.purdue.EDU
Distribution: usa
Organization: Department of Computer Science, Purdue University
Lines: 5

Is the minimum vertex-cover problem for 3-connected
planar graphs  NP-complete? It is known that the
above problem is NP-complete for the planar graph
with no vertex degree exceeding 4. Any help regarding
this will be appreciated.