共查询到20条相似文献,搜索用时 12 毫秒
1.
2.
3.
The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from Kr such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr∗(G,H) as the smallest integer k such that every 2-coloring of the edges of Kr−K1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K2 and K3, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(Tn,Km), R(nK2,mK2) and R(Pn,C4). 相似文献
4.
Size bipartite Ramsey numbers 总被引:1,自引:0,他引:1
Yuqin Sun 《Discrete Mathematics》2009,309(5):1060-1066
Let B, B1 and B2 be bipartite graphs, and let B→(B1,B2) signify that any red-blue edge-coloring of B contains either a red B1 or a blue B2. The size bipartite Ramsey number is defined as the minimum number of edges of a bipartite graph B such that B→(B1,B2). It is shown that is linear on n with m fixed, and is between c1n22n and c2n32n for some positive constants c1 and c2. 相似文献
5.
Xuding Zhu 《Discrete Mathematics》1998,190(1-3):215-222
Suppose G is a graph. The chromatic Ramsey number rc(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 Mn = min[rc(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that Mn = (n − 1)2 + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M6 and M7. 相似文献
6.
Lingsheng Shi 《Journal of Graph Theory》2005,50(3):175-185
The Ramsey number R(G1,G2) of two graphs G1 and G2 is the least integer p so that either a graph G of order p contains a copy of G1 or its complement Gc contains a copy of G2. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
7.
An upper bound on the Ramsey number r(K2,n‐s,K2,n) where s ≥ 2 is presented. Considering certain r(K2,n‐s,K2,n)‐colorings obtained from strongly regular graphs, we additionally prove that this bound matches the exact value of r(K2,n‐s,K2,n) in infinitely many cases if holds. Moreover, the asymptotic behavior of r(K2,m,K2,n) is studied for n being sufficiently large depending on m. We conclude with a table of all known Ramsey numbers r(K2,m,K2,n) where m,n ≤ 10. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 252–268, 2003 相似文献
8.
素数阶循环图和经典Ramsey数R(4,n)的三个新下界 总被引:1,自引:0,他引:1
研究了素数阶循环圈的基本性质,提出了寻求有效参数构造正则循环圈的新方法,得到了3个经典Ramsey数的新下界:R(4,17)≥164,R(4,18)≥182,R(4,22)≥282.这前2个结果填补了关于Ramsey数综述[2]的上下界表中的2个空白,第3个结果超过了目前已知的最好下界R(4,22)≥258, 相似文献
9.
Halina Bielak 《Discrete Mathematics》2009,309(22):6446-6449
P. Erdös, R.J. Faudree, C.C. Rousseau and R.H. Schelp [P. Erdös, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145-161] studied the asymptotic behaviour of for certain graphs G,H. In this paper there will be given a lower bound for the diagonal size Ramsey number of Kn,n,n. The result is a generalization of a theorem for Kn,n given by P. Erdös and C.C. Rousseau [P. Erdös, C.C. Rousseau, The size Ramsey numbers of a complete bipartite graph, Discrete Math. 113 (1993) 259-262].Moreover, an open question for bounds for size Ramsey number of each n-regular graph of order n+t for t>n−1 is posed. 相似文献
10.
In this paper, we show that for any fixed integers and , the star-critical Ramsey number for all sufficiently large . Furthermore, for any fixed integers and , as . 相似文献
11.
The book with n pages Bn is the graph consisting of n triangles sharing an edge. The book Ramsey number r(Bm,Bn) is the smallest integer r such that either Bm ? G or Bn ? G for every graph G of order r. We prove that there exists a positive constant c such that r(Bm,Bn) = 2n + 3 for all n ≥ cm. Our proof is based mainly on counting; we also use a result of Andrásfai, Erd?s, and Sós stating that triangle‐free graphs of order n and minimum degree greater than 2n/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
12.
In this paper, some properties of Ramsey numbers are studied, and the following results are presented.
- 1. (1) For any positive integers k1, k2, …, km l1, l2, …, lm (m> 1), we have .
- 2. (2) For any positive integers k1, k2, …, km, l1, l2, …, ln , we have . Based on the known results of Ramsey numbers, some results of upper bounds and lower bounds of Ramsey numbers can be directly derived by those properties.
13.
14.
The size Ramsey number of two graphs and is the smallest integer such that there exists a graph on edges with the property that every red-blue colouring of the edges of yields a red copy of or a blue copy of . In 1981, Erdős observed that and he conjectured that this upper bound on is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: They proved the case . In 2001, Pikhurko showed that this conjecture is not true for and , by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given and . 相似文献
15.
For fixed integers m,k2, it is shown that the k-color Ramsey number rk(Km,n) and the bipartite Ramsey number bk(m,n) are both asymptotically equal to kmn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number is at most (1+o(1))nm+1/(logn)m-1. Moreover, the order of magnitude of is proved to be nm+1/(logn)m if H≠Km as n→∞. 相似文献
16.
17.
Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function rf (a1, a2, …, ak) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k=2. In this article, we answer an open problem by determining an explicit formula for the general case k>2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164–178, 2010 相似文献
18.
19.
20.
Let brk(C4;Kn, n) be the smallest N such that if all edges of KN, N are colored by k + 1 colors, then there is a monochromatic C4 in one of the first k colors or a monochromatic Kn, n in the last color. It is shown that brk(C4;Kn, n) = Θ(n2/log2n) for k?3, and br2(C4;Kn, n)≥c(n n/log2n)2 for large n. The main part of the proof is an algorithm to bound the number of large Kn, n in quasi‐random graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 47‐54, 2011 相似文献