Large Chromatic Number and Ramsey Graphs

被引：4

作者：

Biro, Csaba ^{[1
]}

Fueredi, Zoltan ^{[2
,3
]}

Jahanbekam, Sogol ^{[2
]}

机构：

[1] Univ Louisville, Dept Math, Louisville, KY 40292 USA

[2] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[3] Hungarian Acad Sci, Renyi Inst Math, H-1364 Budapest, Hungary

来源：

GRAPHS AND COMBINATORICS | 2013年 / 29卷 / 05期

基金：

美国国家科学基金会;

关键词：

Clique number; Chromatic number; Ramsey graphs;

D O I：

10.1007/s00373-012-1179-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let Q (n, chi) denote the minimum clique size an n-vertex graph can have if its chromatic number is chi. Using Ramsey graphs we give an exact, albeit implicit, formula for the case chi a parts per thousand yen (n + 3)/2.

引用

页码：1183 / 1191

页数：9

共 9 条

[1] A NOTE ON RAMSEY NUMBERS
AJTAI, M
KOMLOS, J
SZEMEREDI, E
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1980, 29 (03) : 354 - 360
[2] [Anonymous], 1986, N HOLLAND MATH STUDI
[3] Biro C, 2011, ARXIV11072630
[4] Bogart K. P., 1973, Discrete Mathematics, V5, P33, DOI 10.1016/0012-365X(73)90025-3
[5] Gyarfas A., 2011, ARXIV11083444
[6] Hiraguti T., 1955, Sci. Rep. Kanazawa Univ., V4, P1
[7] THE RAMSEY NUMBER R(3,T) HAS ORDER OF MAGNITUDE T(2)/LOG-T
KIM, JH
[J]. RANDOM STRUCTURES & ALGORITHMS, 1995, 7 (03) : 173 - 207
[8] Liu Gaku, 2012, ELECTRON J COMB, V19, P10
[9] A constructive approach for the lower bounds on the Ramsey numbers R (s,t)
Xu, XD
Zheng, X
Radziszowski, SP
[J]. JOURNAL OF GRAPH THEORY, 2004, 47 (03) : 231 - 239

← 1 →