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 条

[21] Ramsey simplicity of random graphs
Boyadzhiyska, Simona
Clemens, Dennis
Das, Shagnik
Gupta, Pranshu
COMBINATORICS PROBABILITY AND COMPUTING, 2024,
[22] Minimum degree and pan-k-linked graphs
Gould, Ronald J.
Powell, Jeffrey S.
Wagner, Brian C.
Whalen, Thor C.
DISCRETE MATHEMATICS, 2009, 309 (10) : 3013 - 3022
[23] Distance domination in graphs with given minimum and maximum degree
Michael A. Henning
Nicolas Lichiardopol
Journal of Combinatorial Optimization, 2017, 34 : 545 - 553
[24] Spectral radius and traceability of graphs with large minimum degree
Wei, Jia
You, Zhifu
LINEAR & MULTILINEAR ALGEBRA, 2020, 68 (01) : 161 - 176
[25] Non-Hamiltonian Graphs with Large Minimum Degree
Fu, Lingting
Gao, Liqing
Wang, Jian
Yang, Weihua
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2024, 47 (01)
[26] Spectral conditions for graphs to be β-deficient involving minimum degree
Liu, Weijun
Liu, Minmin
Feng, Lihua
LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (04) : 792 - 802
[27] LONG CYCLES IN GRAPHS WITH PRESCRIBED TOUGHNESS AND MINIMUM DEGREE
BAUER, D
BROERSMA, HJ
VANDENHEUVEL, J
VELDMAN, HJ
DISCRETE MATHEMATICS, 1995, 141 (1-3) : 1 - 10
[28] Supereulerian Graphs with Constraints on the Matching Number and Minimum Degree
Mansour J. Algefari
Hong-Jian Lai
Graphs and Combinatorics, 2021, 37 : 55 - 64
[29] On the minimum degree of power graphs of finite nilpotent groups
Panda, Ramesh Prasad
Patra, Kamal Lochan
Sahoo, Binod Kumar
COMMUNICATIONS IN ALGEBRA, 2023, 51 (01) : 314 - 329
[30] Spectral radius and Hamiltonicity of graphs with large minimum degree
Nikiforov, Vladimir
CZECHOSLOVAK MATHEMATICAL JOURNAL, 2016, 66 (03) : 925 - 940

← 1 2 3 4 5 →