Premium
Two graphs without planar covers
Author(s) -
Archdeacon Dan
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10075
Subject(s) - combinatorics , planar graph , mathematics , conjecture , planar , cover (algebra) , discrete mathematics , 1 planar graph , graph , chordal graph , computer science , mechanical engineering , computer graphics (images) , engineering
In this note we prove that two specific graphs do not have finite planar covers. The graphs are K 7 – C 4 and K 4,5 –4 K 2 . This research is related to Negami's 1‐2‐∞ Conjecture which states “A graph G has a finite planar cover if and only if it embeds in the projective plane.” In particular, Negami's Conjecture reduces to showing that 103 specific graphs do not have finite planar covers. Previous (and subsequent) work has reduced these 103 to a few specific graphs. This paper covers 2 of the remaining cases. The sole case currently remaining is to show that K 2,2,2,1 has no finite planar cover. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 318–326, 2002