On the connectivity of infinite graphs

被引:0
|
作者
P. Komjáth
机构
[1] Eötvös Loránd University,Institute of Mathematics
来源
Acta Mathematica Hungarica | 2018年 / 154卷
关键词
infinite graph; chromatic number; connectivity; 03E05; 05C15; 05C40;
D O I
暂无
中图分类号
学科分类号
摘要
Let μ≥ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu \geq \omega}$$\end{document} be regular, assume the Generalized Continuum Hypothesis and the principle □λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\square_\lambda}$$\end{document} holds for every singular λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda}$$\end{document} with cf(λ)≤μ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\rm cf}(\lambda) \leq \mu}$$\end{document}. Let X be a graph with chromatic number greater than μ+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu^+}$$\end{document}. Then X contains a μ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu}$$\end{document}-connected subgraph Y of X whose chromatic number is greater than μ+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu^+}$$\end{document}.
引用
收藏
页码:215 / 222
页数:7
相关论文
共 50 条
  • [31] A Note on Connectivity of Regular Graphs
    Xu, Huixian
    Zhou, Jinqiu
    JOURNAL OF INTERCONNECTION NETWORKS, 2023, 23 (04)
  • [32] Dynamic Connectivity in Disk Graphs
    Alexander Baumann
    Haim Kaplan
    Katharina Klost
    Kristin Knorr
    Wolfgang Mulzer
    Liam Roditty
    Paul Seiferth
    Discrete & Computational Geometry, 2024, 71 (1) : 214 - 277
  • [33] Extremal graphs in connectivity augmentation
    Jordán, T
    JOURNAL OF GRAPH THEORY, 1999, 31 (03) : 179 - 193
  • [34] On the Connectivity of Token Graphs of Trees
    Fabila-Monroy, Ruy
    Leanos, Jesus
    Laura Trujillo-Negrete, Ana
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2022, 24 (01):
  • [35] Dynamic Connectivity in Disk Graphs
    Baumann, Alexander
    Kaplan, Haim
    Klost, Katharina
    Knorr, Kristin
    Mulzer, Wolfgang
    Roditty, Liam
    Seiferth, Paul
    DISCRETE & COMPUTATIONAL GEOMETRY, 2024, 71 (01) : 214 - 277
  • [36] Connectivity of Cartesian products of graphs
    Spacapan, Simon
    APPLIED MATHEMATICS LETTERS, 2008, 21 (07) : 682 - 685
  • [37] Connectivity Graphs of Uncertainty Regions
    Erin Chambers
    Alejandro Erickson
    Sándor P. Fekete
    Jonathan Lenchner
    Jeff Sember
    Venkatesh Srinivasan
    Ulrike Stege
    Svetlana Stolpner
    Christophe Weibel
    Sue Whitesides
    Algorithmica, 2017, 78 : 990 - 1019
  • [38] Connectivity of Cartesian product graphs
    Xu, JM
    Yang, C
    DISCRETE MATHEMATICS, 2006, 306 (01) : 159 - 165
  • [39] THE CONNECTIVITY OF MAXIMUM MATCHING GRAPHS
    LIU Yan(Department of Mathematics
    Journal of Systems Science & Complexity, 2004, (01) : 33 - 38
  • [40] Mixed Connectivity of Random Graphs
    Gu, Ran
    Shi, Yongtang
    Fan, Neng
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I, 2017, 10627 : 133 - 140