Premium
K 6 ‐minors in triangulations and complete quadrangulations
Author(s) -
Mukae Raiji,
Nakamoto Atsuhiro
Publication year - 2009
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.20360
Subject(s) - mathematics , combinatorics , conjecture , triangulation , projective plane , planar , graph , toroid , planar graph , discrete mathematics , geometry , computer science , physics , computer graphics (images) , quantum mechanics , correlation , plasma
In this paper, we shall prove that a projective‐planar (resp., toroidal) triangulation G has K 6 as a minor if and only if G has no quadrangulation isomorphic to K 4 (resp., K 5 ) as a subgraph. As an application of the theorems, we can prove that Hadwiger's conjecture is true for projective‐planar and toroidal triangulations. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 302‐312, 2009