共查询到20条相似文献,搜索用时 31 毫秒
1.
Benny Sudakov 《Random Structures and Algorithms》2005,26(3):253-265
In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph Ks on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph Kr. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph KN, contains either a red copy of G or a blue copy of H. The book with n pages is the graph Bn consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(Bn, Kn) ≤ O(n3/log3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K4‐free graph of order n which has no independent set of size n1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005 相似文献
2.
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. 相似文献
3.
《Discrete Mathematics》2004,274(1-3):125-135
The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, β(B)⩾m or β(R)⩾n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, Γ(B)⩾m or Γ(R)⩾n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, Γ(B)⩾m or β(R)⩾n. Since β(G)⩽Γ(G) for every graph G, u(m,n)⩽v(m,n)⩽r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15. 相似文献
4.
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 相似文献
5.
For given graphs G and H, the Ramsey numberR(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper, we investigate the Ramsey number R(∪G,H), where G is a tree and H is a wheel Wm or a complete graph Km. We show that if n?3, then R(kSn,W4)=(k+1)n for k?2, even n and R(kSn,W4)=(k+1)n-1 for k?1 and odd n. We also show that . 相似文献
6.
Maria Axenovich 《Discrete Mathematics》2008,308(20):4710-4723
For two graphs G and H, let the mixed anti-Ramsey numbers, maxR(n;G,H), (minR(n;G,H)) be the maximum (minimum) number of colors used in an edge-coloring of a complete graph with n vertices having no monochromatic subgraph isomorphic to G and no totally multicolored (rainbow) subgraph isomorphic to H. These two numbers generalize the classical anti-Ramsey and Ramsey numbers, respectively.We show that maxR(n;G,H), in most cases, can be expressed in terms of vertex arboricity of H and it does not depend on the graph G. In particular, we determine maxR(n;G,H) asymptotically for all graphs G and H, where G is not a star and H has vertex arboricity at least 3.In studying minR(n;G,H) we primarily concentrate on the case when G=H=K3. We find minR(n;K3,K3) exactly, as well as all extremal colorings. Among others, by investigating minR(n;Kt,K3), we show that if an edge-coloring of Kn in k colors has no monochromatic Kt and no rainbow triangle, then n?2kt2. 相似文献
7.
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 Cm denote a cycle of length m and Kn a complete graph of order n. In this paper, it is shown that R(C6,K8)=36. 相似文献
8.
Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph Km,n. Erd?s, Simonovits and Sós showed that rb(Kn,K3)=n. In 2004, Schiermeyer determined the rainbow numbers rb(Kn,Kk) for all n≥k≥4, and the rainbow numbers rb(Kn,kK2) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(Km,n,kK2) for all k≥1. 相似文献
9.
For given graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper we investigate the Ramsey number of a disjoint union of graphs . For any natural integer k, we contain a general upper bound, R(kG,H)?R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4, 2n-8 or 2n-6, then R(kSn,Wm)=R(Sn,Wm)+(k-1)n. Furthermore, if |Gi|>(|Gi|-|Gi+1|)(χ(H)-1) and R(Gi,H)=(χ(H)-1)(|Gi|-1)+1, for each i, then . 相似文献
10.
For given two graphs G dan H, the Ramsey number R(G,H) is the smallest positive integer n such that every graph F of order n must contain G or the complement of F must contain H. In [12], the Ramsey numbers for the combination between a star S
n
and a wheel W
m
for m=4,5 were shown, namely, R(S
n
,W
4)=2n−1 for odd n and n≥3, otherwise R(S
n
,W
4)=2n+1, and R(S
n
,W
5)=3n−2 for n≥3. In this paper, we shall study the Ramsey number R(G,W
m
) for G any tree T
n
. We show that if T
n
is not a star then the Ramsey number R(T
n
,W
4)=2n−1 for n≥4 and R(T
n
,W
5)=3n−2 for n≥3. We also list some open problems.
Received: October, 2001 Final version received: July 11, 2002
RID="*"
ID="*" This work was supported by the QUE Project, Department of Mathematics ITB Indonesia
Acknowledgments. We would like to thank the referees for several helpful comments. 相似文献
11.
The concept of a localk-coloring of a graphG is introduced and the corresponding localk-Ramsey numberr
loc
k
(G) is considered. A localk-coloring ofG is a coloring of its edges in such a way that the edges incident to any vertex ofG are colored with at mostk colors. The numberr
loc
k
(G) is the minimumm for whichK
m
contains a monochromatic copy ofG for every localk-coloring ofK
m
. The numberr
loc
k
(G) is a natural generalization of the usual Ramsey numberr
k
(G) defined for usualk-colorings. The results reflect the relationship betweenr
k
(G) andr
loc
k
(G) for certain classes of graphs.This research was done while under an IREX grant. 相似文献
12.
Let G be a bipartite graph, with k|e(G). The zero-sum bipartite Ramsey number B(G, Zk) is the smallest integer t such that in every Zk-coloring of the edges of Kt,t, there is a zero-sum mod k copy of G in Kt,t. In this article we give the first proof that determines B(G, Z2) for all possible bipartite graphs G. In fact, we prove a much more general result from which B(G, Z2) can be deduced: Let G be a (not necessarily connected) bipartite graph, which can be embedded in Kn,n, and let F be a field. A function f : E(Kn,n) → F is called G-stable if every copy of G in Kn,n has the same weight (the weight of a copy is the sum of the values of f on its edges). The set of all G-stable functions, denoted by U(G, Kn,n, F) is a linear space, which is called the Kn,n uniformity space of G over F. We determine U(G, Kn,n, F) and its dimension, for all G, n and F. Utilizing this result in the case F = Z2, we can compute B(G, Z2), for all bipartite graphs G. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 151–166, 1998 相似文献
13.
Robert W. Irving 《Discrete Mathematics》1974,9(3):251-264
The generalised Ramsey number R(G1, G2,..., Gk) is defined as the smallest integer n such that, if the edges of Kn, the complete graph on n vertices, are coloured using k colours C1, C2,..., Ck, then for some i(1≤i≤k) there is a subgraph Gi of Kn with all of its edges colour Ci. When G1=G2=...,Gk=G, we use the more compact notation Rk(G).The generalised Ramsey numbers Rk(G) are investigated for all graphs G having at most four vertices (and no isolates). This extends the work of Chvátal and Harary, who made this investigation in the case k=2. 相似文献
14.
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 ∈ . 相似文献
15.
Xin Ke 《Random Structures and Algorithms》1993,4(1):85-97
The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(Tnd, Tnd) ? c · d2 · n and c · n3 ? r?(Kn, Tnd) ? c(d)·n3 log n for every tree Tnd on n vertices. and maximal degree at most d and a complete graph Kn on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc. 相似文献
16.
Edy Tri Baskoro 《Discrete Mathematics》2005,294(3):275-277
For graphs G and H, the Ramsey numberR(G,H) is the smallest positive integer n such that every graph F of order n contains G or the complement of F contains H. For the path Pn and the wheel Wm, it is proved that R(Pn,Wm)=2n-1 if m is even, m?4, and n?(m/2)(m-2), and R(Pn,Wm)=3n-2 if m is odd, m?5, and n?(m-1/2)(m-3). 相似文献
17.
Arthur Busch Michael Ferrara Stephen G. Hartke Michael Jacobson 《Graphs and Combinatorics》2014,30(4):847-859
A (finite) sequence of nonnegative integers is graphic if it is the degree sequence of some simple graph G. Given graphs G 1 and G 2, we consider the smallest integer k such that for every k-term graphic sequence π, there is some graph G with degree sequence π with \({G_1 \subseteq G}\) or with \({G_2 \subseteq \overline{G}}\) . When the phrase “some graph” in the prior sentence is replaced with “all graphs”, the smallest such integer k is the classical Ramsey number r(G 1, G 2). Thus we call this parameter for degree sequences the potential-Ramsey number and denote it r pot (G 1, G 2). In this paper, we give exact values for r pot (K n , K t ), r pot (C n , K t ), and r pot (P n ,K t ) and consider situations where r pot (G 1,G 2) = r(G 1,G 2). 相似文献
18.
A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅Kk+2,k+2, or k=4r−2 for some integer r≥3 and G≅C5[N2r], where N2r is the empty graph on 2r vertices and C5[N2r] is the graph obtained from C5 by replacing each vertex with a graph isomorphic to N2r. 相似文献
19.
We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph K N contains a monochromatic copy of H. A famous result of Chváatal, Rödl, Szemerédi and Trotter states that there exists a constant c(Δ) such that r(H) ≤ c(Δ)n for every graph H with n vertices and maximum degree Δ. The important open question is to determine the constant c(Δ). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants c and c′ such that $2^{c'\Delta } \leqslant c(\Delta ) \leqslant ^{c\Delta \log ^2 \Delta }$ . We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2 cΔlogΔ . The induced Ramsey number r ind (H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erd?s conjectured the existence of a constant c such that, for any graph H on n vertices, r ind (H) ≤ 2 cnlogn . We move a step closer to proving this conjecture, showing that r ind (H) ≤ 2 cnlogn . This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of logn in the exponent. 相似文献
20.
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 相似文献