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 条
  • [31] K 7-minors in optimal 1-embedded graphs on the projective plane
    Sone, Katsuya
    Suzuki, Yusuke
    [J]. DISCRETE MATHEMATICS, 2024, 347 (09)
  • [32] The order-n minors of certain (n plus k) x n matrices
    Bag, Priyabrata
    Dey, Santanu
    Nagisa, Masaru
    Osaka, Hiroyuki
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 603 : 368 - 389
  • [33] 5-List Coloring Toroidal 6-Regular Triangulations in Linear Time
    Balachandran, Niranjan
    Sankarnarayanan, Brahadeesh
    [J]. ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2023, 2023, 13947 : 134 - 146
  • [34] Relationship Among Triangulations, Quadrangulations and Optimal 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}-Planar Graphs
    Kenta Noguchi
    Yusuke Suzuki
    [J]. Graphs and Combinatorics, 2015, 31 (6) : 1965 - 1972
  • [35] Antibandwidth of complete k-ary trees
    Calamoneri, Tiziana
    Massini, Annalisa
    Toeroek, L'ubomir
    Vrt'o, Imrich
    [J]. DISCRETE MATHEMATICS, 2009, 309 (22) : 6408 - 6414
  • [36] FACTORIZING THE COMPLETE GRAPH K-12 BY COMPUTER
    URLAND, E
    STACHO, L
    [J]. COMPUTERS AND ARTIFICIAL INTELLIGENCE, 1994, 13 (06): : 595 - 601
  • [37] Antimagic orientations for the complete k-ary trees
    Song, Chen
    Hao, Rong-Xia
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (04) : 1077 - 1085
  • [38] The 6-girth-thickness of the complete graph
    Castaneda-Lopez, Hector
    Palomino, Pablo C.
    Ramos-Tort, Andrea B.
    Rubio-Montiel, Christian
    Silva-Ruiz, Claudia
    [J]. AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 856 - 861
  • [39] The theta-complete graph Ramsey number r(θk, K5); k = 7, 8, 9
    Jaradat, A. M. M.
    Baniabedalruhman, A.
    Bataineh, M. S.
    Jaradat, M. M. M.
    [J]. ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2021, (46): : 614 - 620
  • [40] The complete list of Ramsey (2K(2), K-4)-minimal graphs
    Wijaya, Kristiana
    Baskoro, Edy Tri
    Assiyatun, Hilda
    Suprijanto, Djoko
    [J]. ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2015, 3 (02) : 216 - 227
12345