On possible counterexamples to Negami's planar cover conjecture

HLINĚNÝ, Petr a Robin THOMAS. On possible counterexamples to Negami's planar cover conjecture. Journal of Graph Theory. New York: John Wiley & Sons, 2004, roč. 46, č. 3, s. 183-206. ISSN 0364-9024.

Základní údaje

Originální název

On possible counterexamples to Negami's planar cover conjecture

Název česky

O možných protipříkladech k Negamiho hypotéze planárních pokrytí

Autoři

HLINĚNÝ, Petr a Robin THOMAS

Vydání

Journal of Graph Theory, New York, John Wiley & Sons, 2004, 0364-9024

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.460

Organizační jednotka

Fakulta informatiky

UT WoS

000222120100004

Klíčová slova anglicky

graph; planar cover; projective plane; minor

Štítky

graph, minor, planar cover, projective plane

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

A simple graph $\H$ is a cover of a graph $\G$ if there exists a mapping $\varphi$ from $\H$ onto $\G$ such that $\varphi$ maps the neighbors of every vertex $v$ in $\H$ bijectively to the neighbors of $\varphi(v)$ 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.

Česky

...