共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper we show that the Ramsey number R(Cn,Wm)=2n-1 for even m and n?5m/2-1. 相似文献
2.
A.N.M. Salman 《Discrete Applied Mathematics》2007,155(14):1878-1884
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 , where Pn is a path on n vertices and is the graph obtained from the join of K1 and Pm. We determine the exact values of for the following values of n and m: 1?n?5 and m?3; n?6 and (m is odd, 3?m?2n-1) or (m is even, 4?m?n+1); 6?n≤7 and m=2n-2 or m?2n; n?8 and m=2n-2 or m=2n or (q·n-2q+1?m?q·n-q+2 with 3?q?n-5) or m?(n-3)2; odd n?9 and (q·n-3q+1?m?q·n-2q with 3?q?(n-3)/2) or (q·n-q-n+4?m?q·n-2q with (n-1)/2?q?n-4). Moreover, we give lower bounds and upper bounds for for the other values of m and n. 相似文献
3.
An explicit coloring of the edges of Kn is constructed such that every copy of K4 has at least four colors on its edges. As n , the number of colors used is n1/2+o(1). This improves upon the previous bound of O(n2/3) due to Erds and Gyárfás obtained by probabilistic methods. The exponent 1/2 is optimal, since it is known that at least (n1/2) colors are required in such a coloring.The coloring is related to constructions giving lower bounds for the multicolor Ramsey number rk(C4). It is more complicated however, because of restrictions imposed on interactions between color classes.* Research supported in part by NSF Grant No. DMS–9970325. 相似文献
4.
The Ramsey numberr(F, G) is determined in the case whereF is an arbitrary fixed graph andG is a sufficiently large sparse connected graph with a restriction on the maximum degree of its vertices. An asymptotically
correct upper bound is obtained forr(F, T) whereT is a sufficiently large, but otherwise arbitrary, tree. 相似文献
5.
6.
For graphsA andB the relationA(B)
r
1
means that for everyr-coloring of the vertices ofA there is a monochromatic copy ofB inA. Forb (G) is the family of graphs which do not embedG. A familyof graphs is Ramsey if for all graphsBthere is a graphAsuch thatA(B)
r
1
. The only graphsG for which it is not known whether Forb (G) is Ramsey are graphs which have a cutpoint adjacent to every other vertex except one. In this paper we prove for a large subclass of those graphsG, that Forb (G) does not have the Ramsey property.This research has been supported in part by NSERC grant 69-1325. 相似文献
7.
8.
Let H
1,H
2, . . .,H
k+1 be a sequence of k+1 finite, undirected, simple graphs. The (multicolored) Ramsey number r(H
1,H
2,...,H
k+1) is the minimum integer r such that in every edge-coloring of the complete graph on r vertices by k+1 colors, there is a monochromatic copy of H
i
in color i for some 1ik+1. We describe a general technique that supplies tight lower bounds for several numbers r(H
1,H
2,...,H
k+1) when k2, and the last graph H
k+1 is the complete graph K
m
on m vertices. This technique enables us to determine the asymptotic behaviour of these numbers, up to a polylogarithmic factor, in various cases. In particular we show that r(K
3,K
3,K
m
) = (m
3 poly logm), thus solving (in a strong form) a conjecture of Erdos and Sós raised in 1979. Another special case of our result implies that r(C
4,C
4,K
m
) = (m
2 poly logm) and that r(C
4,C
4,C
4,K
m
) = (m
2/log2
m). The proofs combine combinatorial and probabilistic arguments with spectral techniques and certain estimates of character sums.* Research supported in part by a State of New Jersey grant, by a USA Israeli BSF grant and by a grant from the Israel Science Foundation. Research supported by NSF grant DMS 9704114. 相似文献
9.
Nikolay Rangelov Kolev 《Discrete Mathematics》2008,308(18):4263-4266
Let G be a graph and a1,…,ar be positive integers. The symbol G→(a1,…,ar) denotes that in every r-coloring of the vertex set V(G) there exists a monochromatic ai-clique of color i for some i∈{1,…,r}. The vertex Folkman numbers F(a1,…,ar;q)=min{|V(G)|:G→(a1,…,ar) and Kq?G} are considered. Let ai, bi, ci, i∈{1,…,r}, s, t be positive integers and ci=aibi, 1?ai?s,1?bi?t. Then we prove that
F(c1,c2,…,cr;st+1)?F(a1,a2,…,ar;s+1)F(b1,b2,…,br;t+1). 相似文献
10.
We prove that multigraded Betti numbers of a simplicial forest are always either 0 or 1. Moreover a nonzero multidegree appears exactly in one homological degree in the resolution. Our work generalizes work of Bouchat [2] on edge ideals of graph trees. 相似文献
11.
There exists a constant C such that for every d-degenerate graphs G
1 and G
2 on n vertices, Ramsey number R(G
1,G
2) is at most Cn, where is the minimum of the maximum degrees of G
1 and G
2.* The work of this author was supported by the grants 99-01-00581 and 00-01-00916 of the Russian Foundation for Fundamental Research and the Dutch-Russian Grant NWO-047-008-006. The work of this author was supported by the NSF grant DMS-9704114. 相似文献
12.
We give a general method to reduce Hurewicz-type selection hypotheses into standard ones. The method covers the known results of this kind and gives some new ones.Building on that, we show how to derive Ramsey theoretic characterizations for these selection hypotheses. 相似文献
13.
Let c,s,t be positive integers. The (c,s,t)-Ramsey game is played by Builder and Painter. Play begins with an s-uniform hypergraph G 0=(V,E 0), where E 0=Ø and V is determined by Builder. On the ith round Builder constructs a new edge e i (distinct from previous edges) and sets G i =(V,E i ), where E i =E i?1∪{e i }. Painter responds by coloring e i with one of c colors. Builder wins if Painter eventually creates a monochromatic copy of K s t , the complete s-uniform hypergraph on t vertices; otherwise Painter wins when she has colored all possible edges.We extend the definition of coloring number to hypergraphs so that χ(G)≤col(G) for any hypergraph G and then show that Builder can win (c,s,t)-Ramsey game while building a hypergraph with coloring number at most col(K s t ). An important step in the proof is the analysis of an auxiliary survival game played by Presenter and Chooser. The (p,s,t)-survival game begins with an s-uniform hypergraph H 0 = (V,Ø) with an arbitrary finite number of vertices and no edges. Let H i?1=(V i?1,E i?1) be the hypergraph constructed in the first i ? 1 rounds. On the i-th round Presenter plays by presenting a p-subset P i ?V i?1 and Chooser responds by choosing an s-subset X i ?P i . The vertices in P i ? X i are discarded and the edge X i added to E i?1 to form E i . Presenter wins the survival game if H i contains a copy of K s t for some i. We show that for positive integers p,s,t with s≤p, Presenter has a winning strategy. 相似文献
14.
For fixed integersp, q an edge coloring of a complete graphK is called a (p, q)-coloring if the edges of everyK
p
K are colored with at leastq distinct colors. Clearly, (p, 2)-colorings are the classical Ramsey colorings without monochromaticK
p
subgraphs. Letf(n, p, q) be the minimum number of colors needed for a (p, q)-coloring ofK
n
. We use the Local Lemma to give a general upper bound forf. We determine for everyp the smallestq for whichf(n, p, q) is linear inn and the smallestq for whichf(n, p, q) is quadratic inn. We show that certain special cases of the problem closely relate to Turán type hypergraph problems introduced by Brown, Erds and T. Sós. Other cases lead to problems concerning proper edge colorings of complete graphs.Supported by OTKA grant 16414. 相似文献
15.
Summary Let (R
2, 1) denote the graph withR
2 as the vertex set and two vertices adjacent if and only if their Euclidean distance is 1. The problem of determining the chromatic number(R
2, 1) is still open; however,(R
2, 1) is known to be between 4 and 7. By a theorem of de Bruijn and Erdös, it is enough to consider only finite subgraphs of (R
2, 1). By a recent theorem of Chilakamarri, it is enough to consider certain graphs on the integer lattice. More precisely, forr > 0, let (Z
2,r,
) denote a graph with vertex setZ
2 and two vertices adjacent if and only if their Euclidean distance is in the closed interval [r –
,r +
]. A simple graph is faithfully
-recurring inZ
2 if there exists a real numberd > 0 such that, for arbitrarily larger, G is isomorphic to a subgraph of (Z
2,r,
) in which every pair of vertices are at least distancedr apart. Chilakamarri has shown that, ifG is a finite simple graph, thenG is isomorphic to a subgraph of (R
2, 1) if and only ifG is faithfully
-recurring inZ
2. In this paper we prove that(Z
2,r,
) 5 for integersr 1. We also prove a Ramsey type result which states that for any integerr > 1, and any coloring ofZ
2 either there exists a monochromatic pair of vertices with their distance in the closed interval [r –
,r +
] or there exists a set of three vertices closest to each other with three distinct colors. 相似文献
16.
Benny Sudakov 《Combinatorica》2005,25(4):487-498
Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph on s vertices. The main aim of this paper is to provide a new lower bound on the size of the maximum subset of G without a copy of complete graph Kr. Our results substantially improve previous bounds of Krivelevich and Bollobás and Hind.
* Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research
was done while visiting Microsoft Research. 相似文献
17.
Amha Tume Lisan 《Combinatorica》1992,12(3):363-365
In [1] V. Bergelson and N. Hindman used a 6-cell partition of [N]2 to show that one cannot combine their major result with the Milliken-Taylor theorem and asked if one can provide an example with fewer than 6-cells. In this note we show that their 6-cell example can be collapsed into a 5-cell example.The author gratefully acknowledges support from the Council on Research of Louisiana State University. 相似文献
18.
C. R. J. Clapham 《Periodica Mathematica Hungarica》1987,18(4):317-318
19.
20.
Dedicated to the memory of Paul Erdős
We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method
we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1.
Received December 1, 1999
RID="*"
ID="*" Supported by NSF grant DMS-9704114
RID="**"
ID="**" Supported by KBN grant 2 P03A 032 16 相似文献