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
      0 references
      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
      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

      Identifiers