Another two graphs with no planar covers
Petr Hliněný · Journal of Graph Theory · 2001
Abstract A graph H is a cover of a graph G if there exists a mapping φ from V(H) onto V(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. It follows from the results of Archdeacon, Fellows, Negami, and the author that the conjecture holds as long as K1,2,2,2 has no finite planar cover. However, this is still an open question, and K1,2,2,2 is not the only minor‐minimal graph in doubt. Let 𝒞4 (ℰ2) denote the graph obtained from K1,2,2,2 by replacing two vertex‐disjoint triangles (four edge‐disjoint triangles) not incident with the vertex of degree 6 with cubic vertices. We prove that the graphs 𝒞4 and ℰ2 have no planar covers. This fact is used in [P. Hlinĕný, R. Thomas, On possible counterexamples to Negami's planar cover conjecture, 1999 (submitted)] to show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 227–242, 2001