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 条
  • [41] The maximum radius of graphs with given order and minimum degree
    Kim, Byeong Moon
    Rho, Yoomi
    Song, Byung Chul
    Hwang, Woonjae
    DISCRETE MATHEMATICS, 2012, 312 (02) : 207 - 212
  • [42] Spectral radius and Hamiltonicity of graphs with large minimum degree
    Vladimir Nikiforov
    Czechoslovak Mathematical Journal, 2016, 66 : 925 - 940
  • [43] Sufficient conditions on the existence of factors in graphs involving minimum degree
    Jia, Huicai
    Lou, Jing
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2024, 74 (04) : 1299 - 1311
  • [44] Minimum Degree, Independence Number and (a, b, k)-Critical Graphs
    Zhou, Sizhong
    ARS COMBINATORIA, 2013, 108 : 425 - 430
  • [45] Distance domination and generalized eccentricity in graphs with given minimum degree
    Dankelmann, Peter
    Erwin, David J.
    JOURNAL OF GRAPH THEORY, 2020, 94 (01) : 5 - 19
  • [46] Graphs with Odd Girth at Least Seven and High Minimum Degree
    Roland Häggkvist
    Guoping Jin
    Graphs and Combinatorics, 1998, 14 (4) : 351 - 362
  • [47] Domination in Graphs of Minimum Degree at least Two and Large Girth
    Christian Löwenstein
    Dieter Rautenbach
    Graphs and Combinatorics, 2008, 24 : 37 - 46
  • [48] Matchings in 1-planar graphs with large minimum degree
    Biedl, Therese
    Wittnebel, John
    JOURNAL OF GRAPH THEORY, 2022, 99 (02) : 217 - 230
  • [49] A note on 1-planar graphs with minimum degree 7
    Biedl, Therese
    DISCRETE APPLIED MATHEMATICS, 2021, 289 : 230 - 232
  • [50] Toughness and distance spectral radius in graphs involving minimum degree
    Lou, Jing
    Liu, Ruifang
    Shu, Jinlong
    DISCRETE APPLIED MATHEMATICS, 2025, 361 : 34 - 47
12345