On the Minimum Degree of Minimal Ramsey Graphs

被引：15
|
作者：
Szabo, Tibor [1 ]
Zumstein, Philipp [2 ]
Zuercher, Stefanie [2 ]
机构：
[1] McGill Univ, Dept Math & Stat, Montreal, PQ, Canada
[2] ETH, Inst Theoret Comp Sci, Zurich, Switzerland
来源：
JOURNAL OF GRAPH THEORY | 2010年 / 64卷 / 02期
关键词：
Ramsey theory; minimal Ramsey graphs; minimum degree; Ramsey-equivalent; Ramsey-seperable;
D O I：
10.1002/jgt.20445
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We investigate the minimization problem of the minimum degree of minimal Ramsey graphs, initiated by Burr et al. We determine the corresponding graph parameter for numerous bipartite graphs, including bi-regular bipartite graphs and forests. We also make initial progress for graphs of larger chromatic number. Numerous interesting problems remain open. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 64: 150-164, 2010
引用
收藏
页码：150 / 164
页数：15
相关论文
共 50 条
  • [31] GRAPHS OF DEGREE AT LEAST 3 WITH MINIMUM ALGEBRAIC CONNECTIVITY
    Abdi, Maryam
    Ghorbani, Ebrahim
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (03) : 2447 - 2467
  • [32] Non-Hamiltonian Graphs with Large Minimum Degree
    Lingting Fu
    Liqing Gao
    Jian Wang
    Weihua Yang
    Bulletin of the Malaysian Mathematical Sciences Society, 2024, 47
  • [33] Binding Number, Minimum Degree and Bipancyclism in Bipartite Graphs
    SUN Jing
    HU Zhiquan
    Wuhan University Journal of Natural Sciences, 2016, 21 (05) : 448 - 452
  • [34] Connectivity keeping edges in graphs with large minimum degree
    Fujita, Shinya
    Kawarabayashi, Ken-ichi
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (04) : 805 - 811
  • [35] Supereulerian Graphs with Constraints on the Matching Number and Minimum Degree
    Algefari, Mansour J.
    Lai, Hong-Jian
    GRAPHS AND COMBINATORICS, 2021, 37 (01) : 55 - 64
  • [36] Distance domination in graphs with given minimum and maximum degree
    Henning, Michael A.
    Lichiardopol, Nicolas
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (02) : 545 - 553
  • [37] MAXIMAL EXPONENTS OF PRIMITIVE GRAPHS WITH MINIMUM DEGREE 3
    Song, Byung Chul
    Kim, Byeong Moon
    KOREAN JOURNAL OF MATHEMATICS, 2011, 19 (04): : 367 - 379
  • [38] Minimum Degree Conditions for the Proper Connection Number of Graphs
    Christoph Brause
    Trung Duy Doan
    Ingo Schiermeyer
    Graphs and Combinatorics, 2017, 33 : 833 - 843
  • [39] Minimum Degree Conditions for the Proper Connection Number of Graphs
    Brause, Christoph
    Trung Duy Doan
    Schiermeyer, Ingo
    GRAPHS AND COMBINATORICS, 2017, 33 (04) : 833 - 843
  • [40] On minimum degree, leaf number, traceability and Hamiltonicity in graphs
    Mafuta, P.
    Mukwembi, S.
    DISCRETE APPLIED MATHEMATICS, 2017, 221 : 89 - 94
12345