On possible counterexamples to Negami's planar cover conjecture (Q4474283)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2081216
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On possible counterexamples to Negami's planar cover conjecture |
scientific article; zbMATH DE number 2081216 |
Statements
On possible counterexamples to Negami's planar cover conjecture (English)
0 references
4 August 2004
0 references
graph
0 references
planar cover
0 references
projective plane
0 references
minor
0 references
Negami's conjecture
0 references
0.9357022047042848
0 references
0.9253368973731996
0 references
0.9207479953765868
0 references
0.9130239486694336
0 references
A simple graph \(H\) is a cover of a graph \(G\) if there exists a graph homomorphism \(\varphi : H \rightarrow G\) that maps the neighbors of every vertex \(v\) in \(H\) bijectively to the neighbors of \(\varphi(v)\). In 1986 Negami conjectured that a graph \(G\) has a planar cover \(H\) if and only if \(G\) embeds in the projective plane. One direction is obvious: the hard direction is proving that if \(G\) does not embed in the projective plane, then \(G\) does not have a planar cover \(H\). Without too much effort, the problem reduces to showing that the minor-minimal nonprojective-planar graphs do not have a planar cover. Multiple papers on this problem have reduced it to showing that a single graph, \(K_{1,2,2,2}\), does not have a planar cover. Unfortunately, this last case has proven especially difficult. In this paper the authors characterize possible counterexamples to Negami's conjecture. They show that, up to easy modifications, there are at most 16 such examples. If the conjecture is true, then this paper is superfluous. The hope is that by examining why these other possible counterexamles do not have planar covers, one can develop techniques for resolving the entire problem, and so the paper is a helpful addition to the literature.
0 references