Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs

Let be graphs. The multicolor Ramsey number is the minimum integer r such that in every edge‐coloring of by k colors, there is a monochromatic copy of in color i for some . In this paper, we investigate the multicolor Ramsey number , determining the asymptotic behavior up to a polylogarithmic factor for almost all ranges of t and m. Several different constructions are used for the lower bounds, including the random graph and explicit graphs built from finite fields. A technique of Alon and Rödl using the probabilistic method and spectral arguments is employed to supply tight lower bounds. A sample result is for any t and m, where c₁ and c₂ are absolute constants.     

含有大的悬挂树图的Ramseygoodness结论(英文)

设H是阶为n的连通图.在H的某一个顶点上悬挂一棵阶为j的树,得到图H_j,用H_j表示这样的图形族.本文证明:当j充分大时,有r(G,H_j)=(x(G)-1)(n+j-1)+s(G),其中x(G),s(G)分别表示图G的色数和色数剩余.     

Ramsey Theory and Bandwidth of Graphs

 The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log ₂ n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”. Received: September 2, 1998?Final version received: November 29, 1999     

一类拟二面体群的四度Cayley图的正规性

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在AutX中正规.研究了4m阶拟二面体群G=a,b|a~(2m)=b~2=1,a~b=a~(m+1)的4度Cayley图的正规性,其中m=2~r,且r2,并得到拟二面体群的Cayley图的同构类型.     

Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r 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 K_r−K_1,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 K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

正规Cayley图

综述了自１９９０年以来１２－传递图研究的一些新成果,正规Ｃａｙｌｅｙ图的相关结论。     

Size bipartite Ramsey numbers

Let B, B₁ and B₂ be bipartite graphs, and let B→(B₁,B₂) signify that any red-blue edge-coloring of B contains either a red B₁ or a blue B₂. The size bipartite Ramsey number is defined as the minimum number of edges of a bipartite graph B such that B→(B₁,B₂). It is shown that is linear on n with m fixed, and is between c₁n²2ⁿ and c₂n³2ⁿ for some positive constants c₁ and c₂.     

Some Bipartite Ramsey Numbers

Consider a complete bipartite graph K(s, s) with p = 2s points. Let each line of the graph have either red or blue colour. The smallest number p of points such that K(s, s) always contains red K(m, n) or blue K(m, n) is called bipartite Ramsey number denoted by rb(K(m, n), K(m, n)). In this paper, we show that

求Ramsey数下界的循环巧妙图搜索算法研究

本文研究通过构造循环巧妙图而搜寻Ｒａｍｓｅｙ数下界的算法，给出了一个效率较高的算法，该算法已经编程实现，并由此得出了一个具有４６点（４，７）循环巧妙图，从而证明了ｒ（４，７）≥４７。     

New bounds for the distance Ramsey number

In this paper we study the distance Ramsey number $R_D(s,t,d)$. The distance Ramsey number $R_D(s,t,d)$ is the minimum number $n$ such that for any graph $G$ on $n$ vertices, either $G$ contains an induced $s$-vertex subgraph isomorphic to a distance graph in ${\mathbb{R}}^d$ or $\stackrel{?}{G}$ contains an induced $t$-vertex subgraph isomorphic to the distance graph in ${\mathbb{R}}^d$. We obtain the upper and lower bounds on $R_D(s,s,d)$, which are similar to the bounds for the classical Ramsey number $R(?\frac{s}{[d/2]}?,?\frac{s}{[d/2]}?)$.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. 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     

Calculating Ramsey Numbers by Partitioning Colored Graphs

In this article we prove a new result about partitioning colored complete graphs and use it to determine certain Ramsey numbers exactly. The partitioning theorem we prove is that for , in every edge coloring of with the colors red and blue, it is possible to cover all the vertices with k disjoint red paths and a disjoint blue balanced complete ‐partite graph. When the coloring of is connected in red, we prove a stronger result—that it is possible to cover all the vertices with k red paths and a blue balanced complete ‐partite graph. Using these results we determine the Ramsey number of an n‐vertex path, , versus a balanced complete t‐partite graph on vertices, , whenever . We show that in this case , generalizing a result of Erd?s who proved the case of this result. We also determine the Ramsey number of a path versus the power of a path . We show that , solving a conjecture of Allen, Brightwell, and Skokan.     

二面体群D_(2n)的4度正规Cayley图

设G是有限群,S是G的不包含单位元1的非空子集．定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}． Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规．图X称为1-正则的如果它的全自同构群在它的弧集上正则作用．本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类．     

Size Ramsey numbers for some regular graphs

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 K_n,n,n. The result is a generalization of a theorem for K_n,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.     

可定向曲面上具有较短不可收缩圈图嵌入的唯一性

拓扑图论中的一个基本问题就是要决定图在一个(可定向)曲面上的嵌入之数目(既嵌入的柔性问题).H.Whitney的经典结果表明:一个3-连通图至多有一个平面嵌入;C.Thomassen的LEW-嵌入(大边宽度)理论将这一结果推广到一般的可定向曲面.本文给出了几个关于一般可定向曲面上嵌入图的唯一性定理.结果表明:一些具有大的面迹的可定向嵌入仍然具有唯一性.这在本质上推广了C.Thomassen在LEW-嵌入方面的工作.     

ContributionsChromatic Ramsey numbers

Suppose G is a graph. The chromatic Ramsey number r_c(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 M_n = min[r_c(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that M_n = (n − 1)² + 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 M₆ and M₇.     

p~2阶弧传递循环图的正规性条件

群G关于S的有向Cayley图X=Cay(G,S)称为pk阶有向循环图,若G是pk阶循环群.利用有限群论和图论的较深刻的结果,对p2阶弧传递(有向)循环图的正规性条件进行了讨论,证明了任一p2阶弧传递(有向)循环图是正规的当且仅当(|Aut(G,S)|,p)=1.