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 条

[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

← 1 2 3 4 5 →