摘要:

AbstractForn≧k≧ 3, letf(n,Ck) denote the maximum numbermfor which it is possible to color the edges of the complete graphKnwithmcolors in such a way that eachk‐cycleCkinKnhas atleast two edges of the same color. Erdös, Simonovits, and Sós conjectured that for every fixedk≧ 3,f(n, Ck) =n(k–2/2 + 1/k–1) +O(1), and proved it only fork= 3. It is shown thatf(n, C4) =n+ [1/3n] – 1, and the conjecture thus proved fork= 4. Some upper bounds are also obtained f

ISSN:0364-9024    

DOI:10.1002/jgt.3190070112

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1983

数据来源: WILEY

摘要:

Abstractrc(k) Denotes the smallest integer such that anyc‐edge‐coloring of therc(k) vertex complete graph has a monochromatick‐connected subgraph. For anyc, k≧ 2, we show 2c(k– 1) + 1 ≦rc(k)<10/3c(k– 1) + 1, and further that 4(k– 1) + 1 ≧r2(k)<(3 + √ (k– 1) + 1. Some exact values for various Ramsey connectivity numb

ISSN:0364-9024    

DOI:10.1002/jgt.3190070113

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1983

数据来源: WILEY

摘要:

AbstractLet us call a finite subsetXof a Euclideanm‐space EmRamseyif for any positive integerrthere is an integern=n(X;r) such that in any partition of EnintorclassesC1,…,Cr, someCicontains a setX' which is the image ofXunder some Euclidean motion in En. Numerous results dealing with Ramsey sets have been proved in recent years although the basic problem of characterizing the Ramsey sets remains unsettled. The strongest constraints currently known are: (i) Any Ramsey set must lie on the surface of some sphere; (ii) Any subset of the set of vertices of a rectangular parallelepiped is Ramsey. In this paper we examine the corresponding problem in the case that our underlying spaces are (unit)n‐spheresSnand the allowed motions are orthogonal transformations ofSnonto itself. In particular, we show that for subsets ofSnwhich are not too “large,” results similar to (i) and

ISSN:0364-9024    

DOI:10.1002/jgt.3190070114

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1983

数据来源: WILEY

摘要:

AbstractThesize Ramsey number ř(G) of a graphGis the smallest integer ř such that there is a graphFof ř edges with the property thatanytwo‐coloring of the edges ofFyields a monochromatic copy ofG. First we show that the size Ramsey number ř(Pn) of the pathPnof lengthnislinearinn, solving a problem of Erdös. Second we present a general upper bound on size Ramsey numbers of

ISSN:0364-9024    

DOI:10.1002/jgt.3190070115

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1983

数据来源: WILEY

摘要:

AbstractWe survey some results on covering the vertices of 2‐colored complete graphs by two paths or by two cycles of different color. We show the role of these results in determining path Ramsey numbers and in algorithms for finding long monochromatic paths or cycles in 2‐colored complete gra

ISSN:0364-9024    

DOI:10.1002/jgt.3190070116

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1983

数据来源: WILEY

摘要:

AbstractIt is proved that if a graphGhas atleastcnlognvertices, then eitherGor its complementGcontains a subgraphHwith atleastnvertices and minimum degree atleast |V(H)|/2. This result is not far from being best possible, as is shown by a rather unusual random construction. Some related questions are also discussed.

ISSN:0364-9024    

DOI:10.1002/jgt.3190070117

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1983

数据来源: WILEY

摘要:

AbstractA new construction of self‐complementary graphs containing noK10orK11is described. This construction gives the Ramsey number lower boundsr(10,10) ≧ 458 andr(11,11)

ISSN:0364-9024    

DOI:10.1002/jgt.3190070118

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1983

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190070101

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1983

数据来源: WILEY