✦ LIBER ✦

On possible counterexamples to Negami's planar cover conjecture

✍ Scribed by Petr Hliněný; Robin Thomas

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 281 KB
Volume: 46
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10177

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A simple graph H is a cover of a graph G if there exists a mapping φ from H onto G such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ (υ) in G. Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. The conjecture is still open. It follows from the results of Archdeacon, Fellows, Negami, and the first author that the conjecture holds as long as the graph K~1,2,2,2~ has no finite planar cover. However, those results seem to say little about counterexamples if the conjecture was not true. We show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. Moreover, we exhibit a finite list of sets of graphs such that the set of excluded minors for the property of having finite planar cover is one of the sets in our list. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 183–206, 2004

📜 SIMILAR VOLUMES

A note on possible extensions of Negami'

A note on possible extensions of Negami's conjecture

✍ Hlin?n�, Petr 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 2 views

A graph H is a cover of a graph G, if there exists a mapping ϕ from V (H) onto V (G) such that for every vertex v of G, ϕ maps the neighbors of v in H bijectively onto the neighbors of ϕ(v) in G. Negami conjectured in 1987 that a connected graph has a finite planar cover if and only if it embeds in

On a Minimal Counterexample to Dade's Pr

On a Minimal Counterexample to Dade's Projective Conjecture

✍ Charles W. Eaton; Geoffrey R. Robinson 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 96 KB

Counterexamples to faudree and schelp's

Counterexamples to faudree and schelp's conjecture on hamiltonian-connected graphs

✍ Carsten Thomassen 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 291 KB

## Abstract Faudree and Schelp conjectured that for any two vertices __x, y__ in a Hamiltonian‐connected graph __G__ and for any integer __k__, where __n__/2 ⩽ __k__ ⩽ __n__ − 1, __G__ has a path of length __k__ connecting __x__ and __y__. However, we show in this paper that there are infinitely ma

Counterexamples to randić's conjecture o

Counterexamples to randić's conjecture on distance degree sequences for trees

✍ Peter J. Slater 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

## Abstract As counterexamples to a conjecture of Randić, pairs of nonisomorphic trees with the same collections of distance degree sequences are presented.

A Counterexample to Fulton's Conjecture

A Counterexample to Fulton's Conjecture on [formula]0, n

✍ Peter Vermeire 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 67 KB

We describe an elementary counterexample to a conjecture of Fulton on the set of effective divisors on the space M 0 n of marked rational curves.  2002 Elsevier Science (USA)

A Counterexample to Perret's Conjecture

A Counterexample to Perret's Conjecture on Infinite Class Field Towers for Global Function Fields

✍ Harald Niederreiter; Chaoping Xing 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 92 KB

We show by a counterexample that Perret's conjecture on in"nite class "eld towers for global function "elds is wrong, and so Perret's method of in"nite rami"ed class "eld towers in the asymptotic theory of global function "elds with many rational places breaks down.