共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
In this paper we study multipartite Ramsey numbers for odd cycles. We formulate the following conjecture: Let n≥5 be an arbitrary positive odd integer; then, in any two‐coloring of the edges of the complete 5‐partite graph K((n?1)/2, (n?1)/2, (n?1)/2, (n?1)/2, 1) there is a monochromatic Cn, a cycle of length n. This roughly says that the Ramsey number for Cn (i.e. 2n?1 ) will not change (somewhat surprisingly) if four large “holes” are allowed. Note that this would be best possible as the statement is not true if we delete from K2n?1 the edges within a set of size (n+ 1)/2. We prove an approximate version of the above conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 61:12‐21, 2009 相似文献
3.
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 . 相似文献
4.
We determine the maximum number of colors in a coloring of the edges of Km,n such that every cycle of length 2k contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers q≤ a, let g(a,q) be the maximum number of edges in a spanning subgraph G of Ka,a such that the minimum number of vertex‐disjoint even paths and pairs of vertices from distinct partite sets needed to cover V(G) is q. We prove that g(a,q) = a2 ? aq + max {a, 2q ? 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004 相似文献
5.
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.
For given graphs G1,G2,…,Gk, k≥2, the multicolor Ramsey number, denoted by R(G1,G2,…,Gk), is the smallest integer n such that if we arbitrarily color the edges of a complete graph on n vertices with k colors, there is always a monochromatic copy of Gi colored with i, for some 1≤i≤k. Let Pk (resp. Ck) be the path (resp. cycle) on k vertices. In the paper we consider the value for numbers of type R(Pi,Pk,Cm) for odd m, k≥m≥3 and when i is odd, and when i is even. In addition, we provide the exact values for Ramsey numbers R(P3,Pk,C4) for all integers k≥3. 相似文献
8.
Yaojun Chen T.C. Edwin Cheng Zhengke Miao C.T. Ng 《Applied Mathematics Letters》2009,22(12):1875-1876
For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer n such that for any graph G of order n, either G contains G1 or the complement of G contains G2. Let Cn denote a cycle of order n and Wm a wheel of order m+1. It is conjectured by Surahmat, E.T. Baskoro and I. Tomescu that R(Cn,Wm)=2n−1 for even m≥4, n≥m and (n,m)≠(4,4). In this paper, we confirm the conjecture for n≥3m/2+1. 相似文献
9.
For two graphs, G and H, an edge coloring of a complete graph is (G,H)-good if there is no monochromatic subgraph isomorphic to G and no rainbow subgraph isomorphic to H in this coloring. The set of numbers of colors used by (G,H)-good colorings of Kn is called a mixed Ramsey spectrum. This note addresses a fundamental question of whether the spectrum is an interval. It is shown that the answer is “yes” if G is not a star and H does not contain a pendant edge. 相似文献
10.
Ingo Schiermeyer 《Journal of Graph Theory》2003,44(4):251-260
The cycle‐complete graph Ramsey number r(Cm, Kn) is the smallest integer N such that every graph G of order N contains a cycle Cm on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(Cm, Kn) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C3, K3) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n2 ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003 相似文献
11.
Allan Siu Lun Lo 《Journal of Graph Theory》2011,67(2):91-95
The Ramsey number Rk(G) of a graph G is the minimum number N, such that any edge coloring of KN with k colors contains a monochromatic copy of G. The constrained Ramsey number f(G, T) of the graphs G and T is the minimum number N, such that any edge coloring of KN with any number of colors contains a monochromatic copy of G or a rainbow copy of T. We show that these two quantities are closely related when T is a matching. Namely, for almost all graphs G, f(G, tK2) = Rt ? 1(G) for t≥2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:91‐95, 2011 相似文献
12.
13.
14.
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. 相似文献
15.
16.
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). 相似文献
17.
András Gyárfás Miklós Ruszinkó Gábor N. Sárközy Endre Szemerédi 《Journal of Graph Theory》2007,55(2):164-174
In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P2n+1,P2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007 相似文献
18.
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. 相似文献
19.
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. 相似文献
20.
The study of the CO‐irredundant Ramsey numbers t(n1, ···, nk) is initiated. It is shown that several values and bounds for these numbers may be obtained from the well‐studied generalized graph Ramsey numbers and the values of t(4, 5), t(4, 6) and t(3, 3, m) are calculated. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 258–268, 2000 相似文献