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 条

[1] On the minimum degree of minimal Ramsey graphs for multiple colours
Fox, Jacob
Grinshpun, Andrey
Liebenau, Anita
Person, Yury
Szabo, Tibor
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 120 : 64 - 82
[2] ON THE MINIMUM DEGREE OF MINIMAL RAMSEY GRAPHS FOR CLIQUES VERSUS CYCLES
Bishnoi, Anurag
Boyadzhiyska, Simona
Clemens, Dennis
Gupta, Pranshu
Lesgourgues, Thomas
Liebenau, Anita
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (01) : 25 - 50
[3] VERTEX FOLKMAN NUMBERS AND THE MINIMUM DEGREE OF MINIMAL RAMSEY GRAPHS
Han, Hiep
Rodl, Vojtech
Szabo, Tibor
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 826 - 838
[4] Minimal ordered Ramsey graphs
Rollin, Jonathan
DISCRETE MATHEMATICS, 2020, 343 (10)
[5] Minimum degree of minimal (n-10)-factor-critical graphs
Guo, Jing
Zhang, Heping
DISCRETE MATHEMATICS, 2024, 347 (04)
[6] Average eccentricity, minimum degree and maximum degree in graphs
Dankelmann, P.
Osaye, F. J.
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (03) : 697 - 712
[7] Partitioning graphs with linear minimum degree
Ma, Jie
Wu, Hehui
RANDOM STRUCTURES & ALGORITHMS, 2024, 65 (03) : 601 - 609
[8] Cycle lengths and minimum degree of graphs
Liu, Chun-Hung
Ma, Jie
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 128 : 66 - 95
[9] Average eccentricity, minimum degree and maximum degree in graphs
P. Dankelmann
F. J. Osaye
Journal of Combinatorial Optimization, 2020, 40 : 697 - 712
[10] Wiener index in graphs with given minimum degree and maximum degree
Alochukwu, Alex
Dankelmann, Peter
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2021, 23 (01)

← 1 2 3 4 5 →