Repozytorium publikacji - Politechnika Gdańska

Rozpatrujemy grę rozgrywaną na nieskończonej liczbie wierzchołków, w której każda runda polega na wskazaniu krawędzi przez jednego gracza - Budowniczego oraz pokolorowaniu jej przez drugiego gracza - Malarkę na jeden z dwóch kolorów, czerwony lub niebieski. Celem Budowniczego jest zmuszenie Malarki do stworzenia monochromatycznej kopii wcześniej ustalonego grafu H w jak najmniejszej możliwej liczbie ruchów. Zakładamy, że gracze grają optymalnie czyli najlepiej jak można w danym momencie i nie popełniają błędów. Malarka będzie próbowała przeszkodzić Budowniczemu jak długo się tylko da. Taką grę będziemy nazywać ̃(H)-grą. W wersji asymetrycznej tej gry, Malarka unika czerwonej kopii grafu G oraz niebieskiej kopii grafu H. Taką grę będziemy nazywać ̃ (G, H)-grą. Wartością liczby Ramseya on-line ̃(H) - wersja symetryczna lub ̃(G, H) - wersja asymetryczna, jest to minimalna liczba tur, w której gra się zakończy. W rozprawie rozważamy liczby Ramseya on-line dla różnych klas grafów. Wyznaczamy wartości liczb Ramseya on-line ̃(P4, P10), ̃(P4, P11) oraz górne oszacowanie ̃(P4, Pn) dla 12 ≤ n ≤ 22. Ponadto przedstawiamy górne oszacowanie ̃(S3, Pl) dla l ≥ 3 oraz dokładną wartość ෩(S3, P5). Pokazujemy nowe oszacowania z dołu i góry dla liczb ̃(C3, Pk) oraz ̃(C4, Pk) dla odpowiednich k oraz wyznaczamy dokładną wartość ̃(C4, P9).

Autorzy

• dr inż. Renata Zakrzewska link otwiera się w nowej karcie