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
关键词
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 条
[41]   A Rainbow k-Matching in the Complete Graph with r Colors [J].
Fujita, Shinya ;
Kaneko, Atsushi ;
Schiermeyer, Ingo ;
Suzuki, Kazuhiro .
ELECTRONIC JOURNAL OF COMBINATORICS, 2009, 16 (01)
[42]   Total k-domination in Cartesian product of complete graphs [J].
Carballosa, Walter ;
Wisby, Justin .
DISCRETE APPLIED MATHEMATICS, 2023, 337 :25-41
[43]   L(j, k)-labelings of Kronecker products of complete graphs [J].
Haque, Md. Enamul ;
Jha, Pranava K. .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS, 2008, 55 (01) :70-73
[44]   R(K6-e,K4)=30* [J].
James, David ;
Kahan, Elisha ;
Rauer, Erik .
GRAPHS AND COMBINATORICS, 2025, 41 (01)
[45]   The theta-complete graph Ramsey number R(θn, K5)=4n-3 for n=6 and n ≥ 10 [J].
Jaradat, M. M. M. ;
Bataineh, M. S. A. ;
Al Hazeem, N. .
ARS COMBINATORIA, 2017, 134 :177-191
[46]   NEW L( j, k)-LABELINGS FOR DIRECT PRODUCTS OF COMPLETE GRAPHS] [J].
Kim, Byeong Moon ;
Song, Byung Chul ;
Rho, Yoomi ;
Hwang, Woonjae .
TAIWANESE JOURNAL OF MATHEMATICS, 2014, 18 (03) :793-807
[47]   Complete Graph K4 Decomposition into Circuits of Length 4 [J].
Darus, Maizon Mohd ;
Ibrahim, Haslinda ;
Karim, Sharmila ;
Omar, Zurni ;
Ahmad, Nazihah .
PROCEEDINGS OF THE 21ST NATIONAL SYMPOSIUM ON MATHEMATICAL SCIENCES (SKSM21): GERMINATION OF MATHEMATICAL SCIENCES EDUCATION AND RESEARCH TOWARDS GLOBAL SUSTAINABILITY, 2014, 1605 :605-610
[48]   PROBLEM STATEMENTS FOR k-NODE SHORTEST PATH AND k-NODE SHORTEST CYCLE IN A COMPLETE GRAPH [J].
Stetsyuk, P. I. .
CYBERNETICS AND SYSTEMS ANALYSIS, 2016, 52 (01) :71-75
[49]   Classification of book representations of K6 [J].
Rowland, Dana .
JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS, 2017, 26 (12)
[50]   Large Sets of Wrapped K-K Hamilton Cycle Decompositions of Complete Bipartite 3-Uniform Hypergraphs [J].
Zhao, Hongtao ;
Rodger, C. A. .
JOURNAL OF COMBINATORIAL DESIGNS, 2015, 23 (11) :499-508