Some Ramsey-Turan type problems and related questions

被引:15
作者
Schelp, R. H. [1 ]
机构
[1] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA
关键词
Ramsey-Turan Problems; Multipartite arrowing graphs; Minimum degree arrowing graphs; NUMBERS; GRAPHS; CYCLES;
D O I
10.1016/j.disc.2011.09.015
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper the following Ramsey-Turan type problem is one of several addressed. For which graphs G does there exist a constant 0 < c < 1 such that when H is a graph of order the Ramsey number r(G) with delta(H) > c vertical bar H vertical bar, then any 2-edge coloring of H contains a monochromatic copy of G? Specific results, conjectures, and questions with suggested values for c are considered when G is an odd cycle, path, or tree of limited maximum degree. Another variant is to 2-edge color a replacement for the graph K-r(G) by a balanced multipartite graph of approximately the same order with the same consequence, a monochromatic G. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:2158 / 2161
页数:4
相关论文
共 16 条
  • [1] Ajtai M., ERDOS SOS CONJ UNPUB
  • [2] Benevides F.S., MULTIPARTITE R UNPUB
  • [3] Bottcher J., J GRAPH THE IN PRESS
  • [4] Burr S.A., 1975, COLLOQUIA MATH SOC J, V1, P214
  • [5] GRAPHS WITH LINEARLY BOUNDED RAMSEY NUMBERS
    CHEN, GT
    SCHELP, RH
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 57 (01) : 138 - 149
  • [6] Erdos P., 1978, Periodica Mathematica Hungarica, V9, P145, DOI 10.1007/BF02018930
  • [7] Erdos P., 1982, P 13 SE C COMB GRAPH, P283
  • [8] Faudree R. J., 1974, Discrete Mathematics, V8, P313, DOI 10.1016/0012-365X(74)90151-4
  • [9] SIZE RAMSEY NUMBERS FOR SMALL-ORDER GRAPHS
    FAUDREE, RJ
    SHEEHAN, J
    [J]. JOURNAL OF GRAPH THEORY, 1983, 7 (01) : 53 - 55
  • [10] Multipartite Ramsey Numbers for Odd Cycles
    Gyarfas, Andras
    Sarkozyz, Gabor N.
    Schelp, Richard H.
    [J]. JOURNAL OF GRAPH THEORY, 2009, 61 (01) : 12 - 21