共查询到20条相似文献,搜索用时 15 毫秒
1.
Let be the -color Ramsey number of an odd cycle of length . It is shown that for each fixed , for all sufficiently large , where is a constant. This improves an old result by Bondy and Erd?s (1973). 相似文献
2.
3.
The Ramsey number R(G1,G2,…,Gk) is the least integer p so that for any k-edge coloring of the complete graph Kp, there is a monochromatic copy of Gi of color i. In this paper, we derive upper bounds of R(G1,G2,…,Gk) for certain graphs Gi. In particular, these bounds show that R(9,9)6588 and R(10,10)23556 improving the previous best bounds of 6625 and 23854. 相似文献
4.
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 . 相似文献
5.
A method to improve the lower bounds for Ramsey numbers R(k,l) is provided: one may construct cyclic graphs by using cubic residues modulo the primes in the form p=6m+1 to produce desired examples. In particular, we obtain 16 new lower bounds, which are 相似文献
R(6,12)230, R(5,15)242, R(6,14)284, R(6,15)374,R(6,16)434, R(6,17)548, R(6,18)614, R(6,19)710,R(6,20)878, R(6,21)884, R(7,19)908, R(6,22)1070,R(8,20)1094, R(7,21)1214, R(9,20)1304, R(8,21)1328.
6.
Michael Tait 《Discrete Mathematics》2018,341(1):104-108
Let denote that any -coloring of contains a monochromatic . The degree Ramsey number of a graph , denoted by , is . We consider degree Ramsey numbers where is a fixed even cycle. Kinnersley, Milans, and West showed that , and Kang and Perarnau showed that . Our main result is that and . Additionally, we substantially improve the lower bound for for general . 相似文献
7.
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. 相似文献
8.
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). 相似文献
9.
10.
A.N.M. Salman 《Discrete Applied Mathematics》2006,154(9):1429-1436
For two given graphs F and H, the Ramsey number R(F,H) is the smallest positive integer p such that for every graph G on p vertices the following holds: either G contains F as a subgraph or the complement of G contains H as a subgraph. In this paper, we study the Ramsey numbers R(Pn,Fm), where Pn is a path on n vertices and Fm is the graph obtained from m disjoint triangles by identifying precisely one vertex of every triangle (Fm is the join of K1 and mK2). We determine the exact values of R(Pn,Fm) for the following values of n and m: 1?n?5 and m?2; n?6 and 2?m?(n+1)/2; 6?n?7 and m?n-1; n?8 and n-1?m?n or ((q·n-2q+1)/2?m?(q·n-q+2)/2 with 3?q?n-5) or m?(n-3)2/2; odd n?9 and ((q·n-3q+1)/2?m?(q·n-2q)/2 with 3?q?(n-3)/2) or ((q·n-q-n+4)/2?m?(q·n-2q)/2 with (n-1)/2?q?n-5). Moreover, we give nontrivial lower bounds and upper bounds for R(Pn,Fm) for the other values of m and n. 相似文献
11.
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. 相似文献
12.
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. 相似文献
13.
Noga Alon Matija Buci Tom Kalvari Eden Kuperwasser Tibor Szab 《Journal of Graph Theory》2021,96(1):109-128
We introduce a list‐coloring extension of classical Ramsey numbers. We investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For ‐uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well known that the Ramsey number is superexponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques. 相似文献
14.
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 . 相似文献
15.
It is shown that r(F2,Fn)=4n+1 for n≥2, and r(Fs,Fn)≤4n+2s for n≥s≥2. 相似文献
16.
Lingsheng Shi 《Discrete Mathematics》2007,307(2):290-292
The Ramsey number R(G) of a graph G is the least integer p such that for all bicolorings of the edges of the complete graph Kp, one of the monochromatic subgraphs contains a copy of G. We show that for any positive constant c and bipartite graph G=(U,V;E) of order n where the maximum degree of vertices in U is at most , . Moreover, we show that the Ramsey number of the cube Qn of dimension n satisfies . In both cases, the small terms are removed from the powers in the upper bounds of a earlier result of the author. 相似文献
17.
18.
Andrey B. Kupavskii Andrei M. Raigorodskii Maria V. Titova 《Discrete Mathematics》2013,313(22):2566-2574
In this paper we study the distance Ramsey number . The distance Ramsey number is the minimum number such that for any graph on vertices, either contains an induced -vertex subgraph isomorphic to a distance graph in or contains an induced -vertex subgraph isomorphic to the distance graph in . We obtain the upper and lower bounds on , which are similar to the bounds for the classical Ramsey number . 相似文献
19.
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 相似文献
20.
We investigate several bounds for both K2,m−K1,n Ramsey numbers and K2,m−K1,n bipartite Ramsey numbers, extending some previous results. Constructions based on certain geometric structures (designs, projective planes, unitals) yield classes of near-optimal bounds or even exact values. Moreover, relationships between these numbers are also discussed. 相似文献