K6-Minors in Triangulations and Complete Quadrangulations

被引：9

作者：

Mukae, Raiji ^{[1
]}

Nalkamoto, Atsuhiro ^{[1
]}

机构：

[1] Yokohama Natl Univ, Fac Educ & Human Sci, Dept Math, Hodogaya Ku, Yokohama, Kanagawa 2408501, Japan

来源：

JOURNAL OF GRAPH THEORY | 2009年 / 60卷 / 04期

关键词：

triangulation; minor; quadrangulation; complete graph; torus; projective plane; IRREDUCIBLE TRIANGULATIONS; KLEIN BOTTLE; GRAPHS;

D O I：

10.1002/jgt.20360

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 60: 302-312, 2009

引用

页码：302 / 312

页数：11

共 50 条

[21] Small complete minors above the extremal edge density
Shapira, Asaf
Sudakov, Benny
COMBINATORICA, 2015, 35 (01) : 75 - 94
[22] FORCING LARGE COMPLETE (TOPOLOGICAL) MINORS IN INFINITE GRAPHS
Stein, Maya
Zamora, Jose
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) : 697 - 707
[23] Biembeddings of metacyclic groups and triangulations of orientable surfaces by complete graphs
Garnnell, M. J.
Knor, M.
ELECTRONIC JOURNAL OF COMBINATORICS, 2012, 19 (03)
[24] The extremal function for K9 minors
Song, ZX
Thomas, R
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (02) : 240 - 252
[25] The Nonexistence of a (K6-e)-Decomposition of the Complete Graph K29
Hartke, S. G.
Ostergard, P. R. J.
Bryant, D.
El-Zanati, S. I.
JOURNAL OF COMBINATORIAL DESIGNS, 2010, 18 (02) : 94 - 104
[26] MATROID TORIC IDEALS: COMPLETE INTERSECTION, MINORS, AND MINIMAL SYSTEMS OF GENERATORS
Garcia-Marco, Ignacio
Alfonsin, Jorge Luis Ramirez
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (04) : 2267 - 2276
[27] The edge-density for K2,t minors
Chudnovsky, Maria
Reed, Bruce
Seymour, Paul
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (01) : 18 - 46
[28] The Construction of Distinct Circuits of Length Six for Complete Graph K-6
Darus, M. M.
Ibrahim, H.
Karim, S.
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS & STATISTICS, 2015, 53 (01): : 17 - 31
[29] Complete Triangulations of a Given Order Generated from a Multitude of Nonisomorphic Cubic Graphs by Current Assignments
Korzhik, Vladimir P.
JOURNAL OF GRAPH THEORY, 2009, 61 (04) : 324 - 334
[30] Parameterizing the Permanent: genus, apices, minors, evaluation mod 2k
Curticapean, Radu
Xia, Mingji
2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, : 994 - 1009

← 1 2 3 4 5 →