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 条
  • [41] Connectivity and Diameter in Distance Graphs
    Penso, Lucia Draque
    Rautenbach, Dieter
    Szwarcfiter, Jayme Luiz
    NETWORKS, 2011, 57 (04) : 310 - 315
  • [42] On the connectivity of graphs in association schemes
    Kodalen, Brian G.
    Martin, William J.
    ELECTRONIC JOURNAL OF COMBINATORICS, 2017, 24 (04):
  • [43] Connectivity of Strong Products of Graphs
    Simon Špacapan
    Graphs and Combinatorics, 2010, 26 : 457 - 467
  • [44] CONNECTIVITY AND HAMILTONIAN CONNECTEDNESS OF GRAPHS
    ZHU, YJ
    WANG, ZX
    CHINESE SCIENCE BULLETIN, 1993, 38 (01): : 15 - 18
  • [45] Note on the connectivity of line graphs
    Hellwig, A
    Rautenbach, D
    Volkmann, L
    INFORMATION PROCESSING LETTERS, 2004, 91 (01) : 7 - 10
  • [46] δ-Connectivity in Random Lifts of Graphs
    Silas, Shashwat
    ELECTRONIC JOURNAL OF COMBINATORICS, 2017, 24 (01):
  • [47] Connectivity of direct products of graphs
    Wang, Wei
    Xue, Ni-Ni
    ARS COMBINATORIA, 2011, 100 : 107 - 111
  • [48] The spanning connectivity of line graphs
    Huang, Po-Yi
    Hsu, Lih-Hsing
    APPLIED MATHEMATICS LETTERS, 2011, 24 (09) : 1614 - 1617
  • [49] Connectivity in time-graphs
    Acer, Utku Gunay
    Drineas, Petros
    Abouzeid, Alhussein A.
    PERVASIVE AND MOBILE COMPUTING, 2011, 7 (02) : 160 - 171
  • [50] Connectivity of Strong Products of Graphs
    Spacapan, Simon
    GRAPHS AND COMBINATORICS, 2010, 26 (03) : 457 - 467