共查询到20条相似文献,搜索用时 15 毫秒
1.
Mathematical Notes - The chromatic number of a Euclidean space ? n with a forbidden finite set C of points is the least number of colors required to color the points of this space so that no... 相似文献
3.
Czechoslovak Mathematical Journal - Let r(G1, G2) be the Ramsey number of the two graphs G1 and G2. For n1 ? n2 ? 1 let S(n1, n2) be the double star given by $$V\left( {S\left(... 相似文献
4.
We investigate the induced Ramsey number
of pairs of graphs (G, H). This number is defined to be the smallest possible order of a graph Γ with the property that, whenever its edges are coloured
red and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that, for any G and H with , we have
where is the chromatic number of H and C is some universal constant. Furthermore, we also investigate imposing some conditions on G. For instance, we prove a bound that is polynomial in both k and t in the case in which G is a tree. Our methods of proof employ certain random graphs based on projective planes.
Received: October 10, 1997 相似文献
6.
Order - For each positive integer n, let Qn denote the Boolean lattice of dimension n. For posets $P, P^{\prime }$ , define the poset Ramsey number $R(P,P^{\prime })$ to be the least N such that... 相似文献
7.
We show that the Ramsey number is linear for every uniform hypergraph with bounded degree. This is a hypergraph extension of the famous theorem for ordinary graphs which Chvátal et al. [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, Jr., The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), pp. 239–243] showed in 1983. Our proof demonstrates the potential of a new regularity lemma by [Y. Ishigami, A simple regularization of hypergraphs, preprint, arXiv:math/0612838 (2006)]. 相似文献
8.
9.
E.J Cockayne 《Journal of Combinatorial Theory, Series B》1974,17(2):183-187
The Ramsey Number r(G1, G2) is the least integer N such that for every graph G with N vertices, either G has the graph G1 as a subgraph or , the complement of G, has the graph G2 as a subgraph.In this paper we embed the paths Pm in a much larger class of trees and then show how some evaluations by T. D. Parsons of Ramsey numbers r(Pm, K1,n), where K1,n is the star of degree n, are also valid for r(Tm, K1,n) where Tm ∈ . 相似文献
10.
Vites Longani 《Southeast Asian Bulletin of Mathematics》2003,26(4):583-592
Consider a complete bipartite graph K(s, s) with p = 2s points. Let each line of the graph have either red or blue colour. The smallest number p of points such that K(s, s) always contains red K(m, n) or blue K(m, n) is called bipartite Ramsey number denoted by rb(K(m, n), K(m, n)). In this paper, we show that
AMS Subject Classifications (1991): 05C15, 05D10. 相似文献
(2) |
11.
A color pattern is a graph whose edges have been partitioned into color classes. A family of color patterns is a Ramsey family provided there is some sufficiently large integer N such that in any edge coloring of the complete graph KN there is an (isomorphic) copy of at least one of the patterns from . The smallest such N is the Ramsey number of the family . The classical Canonical Ramsey theorem of Erds and Rado asserts that the family of color patterns is a Ramsey family if it consists of monochromatic, rainbow (totally multicolored) and lexically colored complete graphs. In this paper we treat the asymmetric case by studying the Ramsey number of families containing a rainbow triangle, a lexically colored complete graph and a fixed arbitrary monochromatic graph. In particular we give asymptotically tight bounds for the Ramsey number of a family consisting of rainbow and monochromatic triangle and a lexically colored KN. Among others, we prove some canonical Ramsey results for cycles. 相似文献
12.
本文讨论了关于树对完全图删去一些相交的三阶路的广义Ramsey数R(Tm,Kn-tP3)和关路对完全图删去一些不相交的三阶完全图的广义Ramsey数R(Pm,Kn-tK3),获得如下结果:1.如果m≥3,n≥3,那么R(Tm,Kn-tP3)=(m-1)(n-t-1)+1,0≤t≤[n/3].2.若m≥4,n,T≥1,则R(Pm,Kn-tK3)=(m-1)(n+2t-1)+1.从而,这两个结果部分地回答了1983年R.J.Gould和M.S.Jacobson在[1]中提出的未解决问题. 相似文献
13.
For any two-colouring of the segments determined by 3n − 3 points in general position in the plane, either the first colour class contains a triangle, or there is a noncrossing
cycle of length n in the second colour class, and this result is tight. We also give a series of more general estimates on off-diagonal geometric
graph Ramsey numbers in the same spirit. Finally we investigate the existence of large noncrossing monochromatic matchings
in multicoloured geometric graphs.
Research partially supported by Hungarian Scientific Research Grants OTKA T043631 and NK67867. 相似文献
14.
We prove—for sufficiently large n—the following conjecture of Faudree and Schelp:
, for the three-color Ramsey numbers of paths on n vertices.
* The second author was supported in part by OTKA Grants T038198 and T046234.
† Research supported in part by the National Science Foundation under Grant No. DMS-0456401. 相似文献
15.
For bipartite graphs G 1, G 2, . . . ,G k , the bipartite Ramsey number b(G 1, G 2, . . . , G k ) is the least positive integer b so that any colouring of the edges of K b,b with k colours will result in a copy of G i in the ith colour for some i. A tree of diameter three is called a bistar, and will be denoted by B(s, t), where s ≥ 2 and t ≥ 2 are the degrees of the two support vertices. In this paper we will obtain some exact values for b(B(s, t), B(s, t)) and b(B(s, s), B(s, s)). Furtermore, we will show that if k colours are used, with k ≥ 2 and s ≥ 2, then \({b_{k}(B(s, s)) \leq \lceil k(s - 1) + \sqrt{(s - 1)^{2}(k^{2} - k) - k(2s - 4)} \rceil}\) . Finally, we show that for s ≥ 3 and k ≥ 2, the Ramsey number \({r_{k}(B(s, s)) \leq \lceil 2k(s - 1)+ \frac{1}{2} + \frac{1}{2} \sqrt{(4k(s - 1) + 1)^{2} - 8k(2s^{2} - s - 2)} \rceil}\) . 相似文献
16.
In this paper we study three-color Ramsey numbers. Let K
i,j
denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G
1, G
2 and G
3, if r(G
1, G
2)≥s(G
3), then r(G
1, G
2, G
3)≥(r(G
1, G
2)−1)(χ(G
3)−1)+s(G
3), where s(G
3) is the chromatic surplus of G
3; (ii) (k+m−2)(n−1)+1≤r(K
1,k
, K
1,m
, K
n
)≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K
k,m
, K
k,m
, K
n
)≤c(n/logn), and r(C
2m
, C
2m
, K
n
)≤c(n/logn)
m/(m−1)
for sufficiently large n.
Received: July 25, 2000 Final version received: July 30, 2002
RID="*"
ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of
education ministry of China, and the foundations of Jiangsu Province
Acknowledgments. The authors are grateful to the referee for his valuable comments.
AMS 2000 MSC: 05C55 相似文献
17.
Doklady Mathematics - In this work, we study nontrivial generalizations of Ramsey numbers to the case of arbitrary sequences of graphs. For many classes of sequences, exact values or asymptotics of... 相似文献
18.
For a tree T we write and , , for the sizes of the vertex classes of T as a bipartite graph. It is shown that for T with maximum degree , the obvious lower bound for the Ramsey number R(T,T) of is asymptotically the correct value for R(T,T).
Received December 15, 1999
RID=" "
ID=" " The first and third authors were partially supported by NSERC. The second author was partially supported by KBN grant
2 P03A 021 17. 相似文献
19.
For given graphs G 1 and G 2, the Ramsey number R(G 1, G 2) is the least integer n such that every 2-coloring of the edges of K n contains a subgraph isomorphic to G 1 in the first color or a subgraph isomorphic to G 2 in the second color. Surahmat et al. proved that the Ramsey number ${R(C_4, W_n) \leq n + \lceil (n-1)/3\rceil}$ . By using asymptotic methods one can obtain the following property: ${R(C_4, W_n) \leq n + \sqrt{n}+o(1)}$ . In this paper we show that in fact ${R(C_4, W_n) \leq n + \sqrt{n-2}+1}$ for n ≥ 11. Moreover, by modification of the Erd?s-Rényi graph we obtain an exact value ${R(C_4, W_{q^2+1}) = q^2 + q + 1}$ with q ≥ 4 being a prime power. In addition, we provide exact values for Ramsey numbers R(C 4, W n ) for 14 ≤ n ≤ 17. 相似文献
20.