Citation
R. Thomas et Xx. Yu, 4-CONNECTED PROJECTIVE-PLANAR GRAPHS ARE HAMILTONIAN, J COMB TH B, 62(1), 1994, pp. 114-132
Citations number
7
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
62
Issue
1
Year of publication
1994
Pages
114 - 132
Database
ISI
SICI code
0095-8956(1994)62:1<114:4PGAH>2.0.ZU;2-A
Abstract
We prove the result stated in the title (conjectured by Grunbaum) and
a conjecture of Plummer that every graph which can be obtained from a
4-connected planar graph by deleting two vertices is Hamiltonian. The
proofs are constructive and give rise to polynomial-time algorithms. (
C) 1994 Academic Press, Inc