-;># ■ The person charging this material is re- sponsible for its return to the library from which it was withdrawn on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. To renew call Telephone Center, 333-8400 UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN MW 4 U93 L161— O-1096 5/c\ jt : J^ ^Crrl UIUCDCS-R-81-1050 / Generalized Ramsey Numbers for Stars by W. D. Wei and C. L. Liu January 1981 UILU-ENG 81 1704 9 1981 ^03 _ • *l DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS Digitized by the Internet Archive in 2013 http://archive.org/details/generalizedramse1050weiw t Generalized Ramsey Numbers for Stars by W. D. Wei ++ and C. L. Liu Visiting from Department of Mathematics, Sichuan University, People's Republic of China. ■L 4- This work was partially supported by the Office of Naval Research under Contract No. 0NR-N00014-79-C-0775. -2- 1. Introduction In [1], the following generalization of Ramsey Theory for graphs was introduced: Let n and m be two integers such that n > m > 1. Let t denote the binomial coefficient ( ). Given n distinct colors, we order the t subsets of m colors in some arbitrary manner. Let G, , G 2 , ..., G. be graphs. The m-chromatic Ramsey number, denoted r (G,, Gp, ..., G.), is defined to be the least p such that if the edges of the complete graph K are colored in any fashion with m colors, then for some j the subgraph r whose edges are colored with the jth subset of colors contains a G.. In J this paper we determine the generalized Ramsey number r n-i (K i,iy K i,iy ••■• K l,iJ Without loss of generality, we assume that i, _< i« <_ ... <_ i . Furthermore let a,, a ? , ..., a denote the n distinct colors, the n subsets of n-1 colors are ordered as {a 2 , a.,, a«, ..., a }, {a,, a^? a«, ..., a }, {a, , a^j a,, ..., a },..., {a, , o^j a., ..., a ,}. 2. Preliminary Results We state here some general results that are useful in a later section. Theorem 1 : Let | G-j| < J G 2 | < . . . <_ | G | + . Then Vi (G r G 2' •••' Viv! ^ G r G 2' ■■•• Vi^ Furthermore, if |G | _> r ~ 2 (G,, G 2 , ..., G ,), then r n-l (G 1' G 2 J "•• G n } = r n-2 (G 1' G 2' ■••• G n-1 } t | G | denotes the number of vertices in G. -3- n 1 Proof : Let p denote r n ~ 2 (G-j, G 2 , ..., G ,). Suppose we color the edges of K with n colors a,, a , ..., a . If we imagine a-, p I c. n 3 I and a as one color, then there is a (a 2 , a.,, a,, . .., a -. ) - G, , or a (a,, a^ s ...» a n ) - G 2 , or a (ot-, 9 a 2 > a^, ..., a ) - G~, . .., or a (a-j, a 2 , a.y . .., a n _2' a n ^ ~ ^n-1* ^ US Cl < G r G 2- •- G n-l>i P I "f | G I ^i P » we can color K , with n-1 colors a,, a ? , such that there is no (a ?} a~, ..., a , ) - G-, , nor (a,, a-, ..., a ,) - G ? , .. nor (a-j, a 2 , . .., a n _2^ " ^n-T However > this can also be considered as a coloring of K , with n colors a,, a«» ..., a , , a (it just happens that the color a n was never used) such that there is no (a 2 , ou, ..., a ,, ) - G-. , nor (a.j, a^, • .., a n _-|> a n ) " ^2' "'' nor ^ a l' a 2' ***' a n-2' a n^ " ^n-1' nor (a-j, a 2> ..., a -j) - 6 . a n-1 Theorem 2 : For even p, the edges of K can be colored such that there are N edges of color a-,, N edges of color a , ..., N edges of I l n color a at each vertex, where N + N + ... + N = p-1. n a-i a* a For odd p, the edges of K can be colored such that there are N edges of color a,, N edges of color ««» •••» N edges of color a at 2 n each vertex, where N + N + ... + N = p-1, and N , N , ..., N are a l a 2 a n a l a 2 a n all even. Proof : It is well-known that for even p, K can be decomposed into p-1 1 -factors, and for odd p, K can be decomposed into ^— 2-factors -4- Theorem 3: [2] *i, + i*2 - 1 if i-is io both even r l ^1,1^ K l,iy n'-! + i 2 if i-|> i 2 not both even Theorem 4: [3] r2( K l,V K l, V K l,i 3 > r l fKl.1 • K l,i 2 ) if ^^'l +i 2 ^ f * • ] £=1 if 1 3 < ^ - i 2 + 1, (1 r 1 2 .1 3 ) e S 3 if i 3 < ^ - i 2 + 1, .(i r i 2 ,i 3 ) E S 3 where (i,, i' 2 » i' 3 ) e S 3 if and only if i, + i" 2 + i 3 2|i 1 i 2 i 3 . 3 (mod 4) , and 3. Determination of r , Lemma 1 : Suppose the edges of K are colored in such a way that at each vertex there is N edges of color a,, N edges of color a . a, 1 a ? 2 ..., N edges of color a . If a B n n N > p - i a l ~ I > p - i 9 a« — 2 N > P " l' a n n then there is no (a,,, a 3 , . . . , a ) - K, . , nor (a,, a 3 , ' a n } ■ K l,i 2 ' • , nor (a ( , otp, . . • » a i ) n-r 1 ,i p n -5- means Proof: For j = 1 , 2, . . . , n N > p - i. (p-1) - N 0. Proof: We note that P - in = H^ - )- 1 - i 1 n-1 1 z i - (n-1) i' - 1 £ = 1 l _ n-1 v 'n d' - D + 1 n-1 J 1 n-1 z i n - (n-1) i a. - 1 Since 2 tt i , it is not possible that i-, = i 9 = ... = i = 1. Thus, 2,=! l i > 2. It follows that n — s^V 1 ' >° Also, n-1 n-1 z i - (n-1) i £ = 1 * > Consequently, P - i -, > - 1 Becaus e p - i, is an integer, we have p - 1^ > 0, -6- Lemma 3: Suppose i P = { n-1 n E i i 1 l AM% i- - 1 Then for a=l Proof: We note that 1„ 1 o. p - 1 n^il 1 * - 1 n 1 I""' . z i\ \- 1 i n-1 n l - (n " 2)i n However, since i < 1 n-1 Thus I 1*1 ** " ' n-1 2 1 £ - (n-2)i n > 1 &=1 p - i n > -1 Because p - i is an integer, we have p-i n >0. Lemma 4: r n-l< K T,y K l,i 2 K l,i n >i ^iA- 1 ] + 1 Proof : Consider an arbitrary coloring of K . Let N (1 <_ j <_ n) be the number of a- edges, respectively, incident with a vertex. In order that there is no (ao»ao» •••» a ) - K, . , nor (a-., a 3 » ..., a ) - K, . , . nor (a-,, ao: t •.) - K, . , we must have -7- N > p - i, a-i — I N > p - i (1) N > p - i a n n at each vertex. Adding the n inequalities in (1), we have n (p-1) >_ np - e i *=1 I J or (n-l)p < £ i - 1 *=1 % Since p is an integer, we must have n P 1 H^\ - ' J It follows that Ci ( V V ■•■• i n ) 1 n Ui 1 '* " ' + 1 Theorem 5: For i, < 1« < ... < i I — c — — n n-1 n-1 1,1 1 1,1 2 ''Vl n-1 'W if i > n — n »Kv*- r + 1 "Hv« - 1 if '„ i n l n-1 - 2 U=i v (i r ....i n ) es n 1 1 / n_i if i < -^ z 1 \ / (~ -8- where (i,, . .., i ) e S p iff i-j + i 2 + ••• + i" = n (mod 2(n-l)) and TT 1 £ = 1 Z ' Proof : The theorem is proved by induction on n. Theorem 3 and 4 provide the basis of induction. We now carry the induction step. Let us examine three cases: Case 1 : i > 1 VI 'a=7* ■ + 1. According to Lemma 4, we have Ci (K i,y k i,t 2 ' ■••• k i,t n-1 , . . . , K, . ) - r 9 ( K-, . , K-. . , . . . , K, . ) n-2 v '"l ,1-, ' ,N l,i 2 l,i n-1 Case 2 : 1 < n — 1 'n-1 -^ItV*-' and (i-j, i' 2 , ..., i' n ) E S n We show that in any coloring of K where p [HM\- there exists either a (ou* a^, •••» a ) - K, . , or a (a,, a^, . ..» a ) K, • , ... or a (a, , a«» •••> a n _-|) " K-. • . We note first that because n Si = n mode 2(n-l), p is an odd number. Suppose there is a coloring of K such that there is no (a 9 , a,, . . . , a ) - K, • , nor (a,, a,, ..., a ) - K, . , ..., nor (a,, a 2 , ..., a n _i) " K-i a ■ At each vertex of K , we must have (p-l) -N^ <1, - 1 (P-U-N <1 2 -1 (2) (P-D "N a <1 n -l n -9- Adding the n inequalities in (2), we obtain n n(p-l) - (p-1) < Ei - n 1 l or Since i / n N i n I TvTi E \ ~ v = rPT E ^£ " ^M in tnis case > a11 the inequalities in (2) must be satisfied with equalities Since 2 ■n i , at least one of i,, i 9 , ..., i must be even, n=l * n Suppose i. is even. In that case, according to the relation J (p-1) - M = U - 1 a. j N must be odd. Now, the total number of edges colored with color i. is a . i p x N which is not an integer because both p and N are odd. Consequently, at one of the vertex in K , the inequalities in (1) can not all be satisfied. Thus, Ci< K i, V K i,y •••• K i,i n > 4^Ji 1p "il - Consider now the following way of coloring K where r ■1*0,'. -Or 1. Let N = p - i a l N = p - i . + 1 j = 2, 3 n-1 at each vertex. According to Lemma 2, N > 0. According to Lemma 3, a-i — 1 n N > for i = 2, 3, . . . , n-1 . It can readily be checked that E N p-1 -10- Since p is even, according to Theorem 2, there exists a coloring of K such that there is no (cu, cu, . .., a ) - K, . , nor (a,, ou, ..., a ) - K, . . .., nor (a^, a 2 » ..., a n _-j) - K-j j . We thus conclude that r , (k, . , K, .,..., K, . ) = n- 1 ' » ' i ' » ' o n ^uv*- 1 Case 3: i < n — n-1 n-2 ii - 1 £=1 and (i-j , i' 2 , ..., i n ) £ S n According to Lemma 4 r n-l ( V V ••" V 1 n i ..V* " We now show ways to color K where p = —* I" V*=i + 1 V 1 such that there is no (a 9 , ou> ...» a) - K, . , nor (a,, a Q , ..., a ) - K hr\ y VJlo 1.1 V "3 : 1,i nor 1 ' " " '"2 (a,, a 9 , ..., a , ) - K-, . . We consider two possibilities: (i) E i = mod (n-1) . In this case, p = -r-A z i ] - 1 . *=i £ n "'^=i y If p is even, one can immediately check that there exists a coloring of K such that N = p - i. a j J N = p - i . + 1 a j J j = 1, 2 3 < j < n at each vertex by noting that E N = p-1 and N _> for j = 1, 2, .. j-l a J a J If p is odd, we can color a complete subgraph K -, such that N ' = p - i. a. J n; = P - i + i 1 < j < 3 4 < j < n in K t where N ' denotes the number of edges colored with color a- at e^jery p-1 a. 3 J -11- vertex in K , . For the remaining vertex in K , the edges incident p-1 p 3 P- with it are to be colored such that I -P-Ij J -1.2 •••» O £ S implies that i- is odd for j = 1, 2, ..., n. According to Theorem 2 there is a coloring of K such that there are N edges of color a- for j = 1 , 2, . . . , n at each J vertex. For the case 2 <_ a <_ n - 2, we can color a subgraph K -, such that N'=p-i- l • ••> i that are even, and e. is equal to 1 if t is even and positive, and is equal to 2 otherwise, suggest the possibility of determining the value r"(K, ., K, .,..., K, . ) for m '>'] I » i p '^n 1 < m < n-1 . -13- References 1. K. M. Chung and C. L. Liu, A Generalization of Ramsey Numbers for Graphs, Discrete Mathematics (1978), 117-127. 2. F. Harary, Recent Results on Generalized Ramsey Theory Graphs, Graph Theory and Applications (Y. Alavi, D. R. Lick, and A. T. White, eds.), Springer-Verlag, Berlin, 1972. 3. K. M. Chung, M. L. Chung, and C. L. Liu, A Generalization of Ramsey Theory for Graphs—With Stars and Complete Graphs as Forbidden Subgraphs, The Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, 1977. 4. Burr, S. A., and J. S. Roberts, "On Ramsey Number for Stars", Utilitas Math. 4(1973), 217-220. BIBLIOGRAPHIC DATA SHEET 1. Report No. UIUCDCS-R-81-1050 2. 3. Recipient's Accession No. 4. Title and Subtitle Generalized Ramsey Numbers for Stars 5. Report Date January 1981 6. 7. Author(s) W. D. Wei and C. L. Liu 8. Performing Organization Rept. No. 9. Performing Organization Name and Address Department of Computer Science University of Illinois 222 Digital Computer Lab Urbana, IL 61801 10. Project/Task/Work Unit No. 11. Contract/Grant No. 0NR-N00014-79-C-9775 12. Sponsoring Organization Name and Address Office of Naval Research Arlington, VA 22217 13. Type of Report & Period Covered 14. 15. Supplementary Notes 16. Abstracts The n-1 chromatic generalized Ramsey number for n stars was determined. 17. Key Words and Document Analysis. 17a. Descriptors Ramsey numbers, graph coloring. 17b. Identifiers/Open-Ended Terms 17c. COSAT1 Field/Group 18. Availability Statement 19. Security Class (This Report) UNCLASSIFIED 21. No. of Pages 15 20. Security Class (This Page UNCLASSIFIED 22. Price FORM NTIS-35 (10-70) USCOMM-DC 40329-P7 1