共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
《Discrete Mathematics》1986,61(1):115-118
The ith Ramsey number for matchings is determined. In addition, our results lead to the calculation of the Ramsey index for matchings. 相似文献
4.
5.
P.E. Haxell 《Journal of Combinatorial Theory, Series A》2006,113(1):67-83
Let Cn denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v1,…,vn and edges v1v2v3, v3v4v5, v5v6v7,…,vn-1vnv1. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of Cn, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible. 相似文献
6.
Fabrıcio Siqueira Benevides 《Journal of Graph Theory》2012,71(3):293-316
In this article we study multipartite Ramsey numbers for odd cycles. Our main result is the proof that a conjecture of Gyárfás et al. (J Graph Theory 61 (2009), 12–21), holds for graphs with a large enough number of vertices. Precisely, there exists n0 such that if n?n0 is a positive odd integer then any two‐coloring of the edges of the complete five‐partite graph K(n ? 1)/2, (n ? 1)/2, (n ? 1)/2, (n ? 1)/2, 1 contains a monochromatic cycle of length n. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
7.
P. Erdős R. J. Faudree C. C. Rousseau R. H. Schelp 《Periodica Mathematica Hungarica》1978,9(1-2):145-161
Let denote the class of all graphsG which satisfyG(G
1,G
2). As a way of measuring minimality for members of, we define thesize Ramsey number (G
1,G
2) by.We then investigate various questions concerned with the asymptotic behaviour of. 相似文献
8.
A link between Ramsey numbers for stars and matchings and the Erd
s-Ginzburg-Ziv theorem is established. Known results are generalized. Among other results we prove the following two theorems. Theorem 5. Let m be an even integer. If c : e (K2m−1)→{0, 1,…, m−1} is a mapping of the edges of the complete graph on 2m−1 vertices into {0, 1,…, m−1}, then there exists a star K1,m in K2m−1 with edges e1, e2,…, em such that c(e1)+c(e2)++c(em)≡0 (mod m). Theorem 8. Let m be an integer. If c : e(Kr(r+1)m−1)→{0, 1,…, m−1} is a mapping of all the r-subsets of an (r+1)m−1 element set S into {0, 1,…, m−1}, then there are m pairwise disjoint r-subsets Z1, Z2,…, Zm of S such that c(Z1)+c(Z2)++c(Zm)≡0 (mod m). 相似文献
9.
《Discrete Mathematics》2022,345(5):112801
Let G and H be simple graphs. The Ramsey number is the minimum integer N such that any red-blue-coloring of edges of contains either a red copy of G or a blue copy of H. Let denote m vertex-disjoint copies of . A lower bound is that . Burr, Erd?s and Spencer proved that this bound is indeed the Ramsey number for , and . In this paper, we show that this bound is the Ramsey number for and . We also show that this bound is the Ramsey number for and . 相似文献
10.
David Rolnick 《Discrete Mathematics》2013,313(20):2084-2093
11.
For bipartite graphs , the bipartite Ramsey number is the least positive integer so that any coloring of the edges of with colors will result in a copy of in the th color for some . In this paper, our main focus will be to bound the following numbers: and for all for and for Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result. 相似文献
12.
13.
The Ramsey size number of dipaths 总被引:1,自引:0,他引:1
David Reimer 《Discrete Mathematics》2002,257(1):173-175
14.
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). 相似文献
15.
Arès Méroueh 《Journal of Graph Theory》2019,90(2):172-188
Let be the Ramsey number of an -uniform loose cycle of length versus an -uniform clique of order . Kostochka et al. showed that for each fixed , the order of magnitude of is up to a polylogarithmic factor in . They conjectured that for each we have . We prove that , and more generally for every that . We also prove that for every and , if is odd, which improves upon the result of Collier-Cartaino et al. who proved that for every and we have . 相似文献
17.
The -color bipartite Ramsey number of a bipartite graph is the least integer for which every -edge-colored complete bipartite graph contains a monochromatic copy of . The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2-color Ramsey number of paths. In this paper we determine asymptotically the 3-color bipartite Ramsey number of paths and (even) cycles. 相似文献
19.
H. Bielak 《Periodica Mathematica Hungarica》1987,18(1):27-38
In this paper we prove that the cyclomatic number of a graph whose every 2-edgecolouring contains a monochromatic path witht edges is not less than 3t/4 ? 2. This fact leads to a simple non-probabilistic proof of the following theorem of Beck: $$\begin{array}{*{20}c} {lim inf{{\hat r\left( {P_t } \right)} \mathord{\left/ {\vphantom {{\hat r\left( {P_t } \right)} t}} \right. \kern-\nulldelimiterspace} t} \geqslant {9 \mathord{\left/ {\vphantom {9 4}} \right. \kern-\nulldelimiterspace} 4},} & {t \to \infty ,} \\ \end{array}$$ where \(\hat r(P_t )\) is the size Ramsey number of a pathP t ont edges. We also show that the size Ramsey number of a (q + 1)-edge star with a tail of length one equals 4q ? 2, i.e., it is linear on the number of edges of the graph. Finally, we calculate that the upper bound for the size Ramsey number of a (q + 2)-edge star with a tail of length two is not greater than 5q + 3. 相似文献
20.
Izolda Gorgol 《Discrete Mathematics》2008,308(19):4389-4395
For two given graphs G and H the planar Ramsey number PR(G,H) is the smallest integer n such that every planar graph F on n vertices either contains a copy of G or its complement contains a copy H. By studying the existence of subhamiltonian cycles in complements of sparse graphs, we determine all planar Ramsey numbers for pairs of cycles. 相似文献