K6‐minors in triangulations and complete quadrangulations |
| |
| Authors: | Raiji Mukae Atsuhiro Nakamoto |
| |
| Affiliation: | Department of Mathematics Faculty of Education and Human Sciences Yokohama National University 79‐2 Tokiwadai, Hodogaya‐KU, Yokohama 240‐8501, Japan |
| |
| Abstract: | In this paper, we shall prove that a projective‐planar (resp., toroidal) triangulation G has K6 as a minor if and only if G has no quadrangulation isomorphic to K4 (resp., K5 ) 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 |
| |
| Keywords: | triangulation minor quadrangulation complete graph torus projective plane |
|
|
