Liczby Ramseya z cyklem C4

Dla grafów H_1, H_2, ..., H_m grafowa liczba Ramseya R(H_1,H_2,...,H_m) to najmniejsza liczba naturalna n taka, że dla dowolnego m-kolorowania krawędziowego grafu pełnego G=K_n istnieje i (1<=i<=m) takie, że graf G zawiera podgraf izomorficzny z H_i, którego wszystkie krawędzie są w kolorze i. W rozprawie rozważamy grafowe liczby Ramseya, których jednym z parametrów jest cykl C_4. Rozpoczniemy (rozdział 1) od omówienia wybranych znanych wyników dla klasycznych liczb Ramseya (gdy grafy H_i są klikami) oraz dwu- i wielokolorowych grafowych liczb, których przynajmniej jednym parametrem jest cykl. W rozdziale 3 rozpatrzymy liczby postaci R(C_4,K_{2,n}) wyznaczając dokładne wartości dla n=14, 15, 18, 38 oraz dowodząc górne oszacowanie, które w nieskończenie wielu przypadkach poprawia wynik otrzymany przez Harbortha i Mengersen. Dokładniej, pokażemy, że jeżeli n>=2 jest parzyste, q=ceil(sqrt(n)) nieparzyste oraz n-(q-1)^2 <= q/2, to R(C_4, K_{2,n})<=n+2q-1. W rozdziale 4 omówimy liczby R(C_4, W_n), gdzie W_n jest kołem o n wierzchołkach. Pokażemy, że dla każdej liczby naturalnej n>=11, R(C_4, W_n) <= n+floor(sqrt(n-2))+1. Wynik ten poprawia dotychczas znane górne oszacowanie uzyskane przez Surahmata i innych. Dodatkowo, za pomocą modyfikacji grafów Erdosa-Renyiego, pokażemy, ze R(C_4, W_q^2 + 1) = q^2 + q + 1, gdzie q>=4 jest potęgą liczby pierwszej. W rozdziale 5 omówimy trój- i czterokolorowe liczby Ramseya, których przynajmniej jednym z parametrów jest cykl C_4 a jako pozostałe parametry przyjmiemy dowolne grafy o maksymalnie czterech wierzchołkach. Za pomocą metod kombinatorycznych oraz algorytmów komputerowych wyznaczymy wartości liczb R(C_4, C_4, B_2)=16, R(C_4, B_2, K_3)=R(C_4, B_2, K_3+e)=17, R(C_4, B_2, B_2)=19 oraz wyznaczymy szereg oszacowań nieznanych dotychczas liczb. Rozprawa została częściowo sfinansowana ze środków Narodowego Centrum Nauki przyznanych na podstawie decyzji numer DEC-2012/05/N/ST6/03063.

For given graphs H_1, H_2, ..., H_m graph Ramsey number R(H_1,H_2,...,H_m) is the smallest integer n such that if we arbitrarily color the edges of the complete graph of order n with m colors, then it contains a monochromatic copy of H_i in color i, for some 1 <= i <= m. In presented dissertation we consider graph Ramsey numbers for quadrilateral (with C_4 as one of the parameters). First, in Chapter 1, we present selected known results for classical Ramsey numbers (when graphs H_i are cliques) and for two and multicolor graph Ramsey numbers involving cycles. In Chapter 3, we consider Ramsey numbers R(C_4,K_{2,n}) and prove upper bounds which in infinitely many cases improve results of Harborth and Mengersen. Specifically, we show that if $n$ is even, q=ceil(sqrt(n)) is odd, and n-(q-1)^2 <= q/2, then R(K_{2,2},K_{2,n}) <= n+2q-1. The latter bound gives the exact value R(C_4,K_{2,18})=27 and R(C_4,K_{2,38})=51. Moreover, we show that R(C_4,K_{2,14})=22 and R(C_4,K_{2,15})=24. In Chapter 4, we consider Ramsey number of C_4 versus wheel of order n. We show that R(C_4, W_n) <= n + floor(sqrt(n-2)) +1, for n>=11. This result improve results of Surahmat et al. Moreover by modification of the Erdos-Renyi graphs we obtain the exact value R(C_4, W_{q^2+1}) = q^2 + q + 1, for q >= 4 being a prime power. In addition, we provide the exact values of Ramsey numbers R(C_4,W_n), for 13 <= n <= 17. In the last chapter we consider 3 and 4-color Ramsey numbers involving C_4 and graphs with at most four vertices. Using combinatorial methods and computer algorithms we obtain exact values of R(C_4,C_4,B_2)=16, R(C_4,B_2,K_3)=R(C_4,B_2,K_3+e)=17, R(C_4,B_2,B_2)=19, and improve upper and lower bounds for several other multicolor Ramsey number. This research was partially funded by the Polish National Science Centre (contract number DEC-2012/05/N/ST6/03063).