Chromatic Ramsey numbers

被引:11
作者
Zhu, XD [1 ]
机构
[1] Natl Sun Yat Sen Univ, Dept Math Appl, Kaohsiung 80424, Taiwan
关键词
D O I
10.1016/S0012-365X(98)00047-8
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Suppose G is a graph. The chromatic Ramsey number r(c)(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let M-n = min{r(c)(a) : chi(G) = n} It was conjectured by Burr et al. (1976) that M-n = (n - 1)(2) + 1. This conjecture has been confirmed previously for n less than or equal to 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M-6 and M-7. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:215 / 222
页数:8
相关论文
共 14 条
  • [1] Burr SA., 1976, ARS Combin, V1, P167
  • [2] ON THE CHROMATIC NUMBER OF THE PRODUCT OF GRAPHS
    DUFFUS, D
    SANDS, B
    WOODROW, RE
    [J]. JOURNAL OF GRAPH THEORY, 1985, 9 (04) : 487 - 495
  • [3] THE CHROMATIC NUMBER OF THE PRODUCT OF 2 4-CHROMATIC GRAPHS IS 4
    ELZAHAR, M
    SAUER, NW
    [J]. COMBINATORICA, 1985, 5 (02) : 121 - 126
  • [4] Graham R.L., 1980, Ramsey Theory, V2nd
  • [5] ON MULTIPLICATIVE GRAPHS AND THE PRODUCT CONJECTURE
    HAGGKVIST, R
    HELL, P
    MILLER, DJ
    LARA, VN
    [J]. COMBINATORICA, 1988, 8 (01) : 63 - 74
  • [6] HEDETNIEMI ST, 1966, 03105447 U MICH
  • [7] MULTIPLICATIVITY OF ORIENTED CYCLES
    HELL, P
    ZHOU, HH
    ZHU, XD
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 60 (02) : 239 - 253
  • [8] HELL P, 1993, COMBINATORICA, V13, P57
  • [9] AN APPROACH TO HEDETNIEMIS CONJECTURE
    SAUER, NW
    ZHU, X
    [J]. JOURNAL OF GRAPH THEORY, 1992, 16 (05) : 423 - 436
  • [10] Multiplicativity of acyclic local tournaments
    Zhou, HS
    Zhu, XD
    [J]. COMBINATORICA, 1997, 17 (01) : 135 - 145