Praca magisterska będzie polegała na prowadzeniu badań naukowych w jednym z poniżej opisanych tematów.
Hipteza 1/3 - 2/3.
Ograniczenie wartości hat guessing number dla grafów rzadkich.
Badamy liczbę chromatyczną kapeluszy grafu, definiowaną w następujący sposób: na każdym wierzchołku grafu G znajduje się jeden gracz, a przeciwnik umieszcza na głowie każdego gracza kapelusz w jednym z K kolorów. Dwóch graczy może widzieć swoje kapelusze tylko wtedy, gdy znajdują się na sąsiadujących wierzchołkach. Wszyscy gracze jednocześnie próbują odgadnąć kolor swojego kapelusza. Gracze nie mogą się ze sobą komunikować, ale wspólnie ustalają strategię przed założeniem kapeluszy. Kapeluszowa liczba chromatyczna oznaczana przez HG(G), to największa liczba K kolorów, dla której gracze są w stanie opracować strategię, która zagwarantuje, że niezależnie od rozmieszczenia kapeluszy przynajmniej jeden z graczy zgadnie poprawnie.
Celem badań byłoby znalezenie najlepszych górnych ograniczeń dla pewnych klas grafów rzadkich.
Bibliografia
- A. Latyshev, K. Kokhas. Hat guessing number for the class of planar graphs is at least 22.
Discrete Mathics. 347(3), 113820. (2024). - J. Chizewer, I.M.J. McInnis, M. Sohrabi, S. Kaistha. The Hat Guessing Number of Cactus Graphs and Cycles. arXiv:2312.00928. (2023).
- C. Knierim, A. Martinsson and R.M. Steiner. Hat guessing numbers of strongly degenerate graphs, SIAM Journal on Discrete Mathematics. 37(2). 1331-1347. (2023).
- A. Latyshev, K. Kokhas, Konstantin. The Hats game. On maximum degree and diameter. Discrete Mathematics. 345(7). 112868. (2022).
- N. Alon, J. Chizewer. On the hat guessing number of graphs. Discrete Mathematics. 345(4). 112785. (2022).
- B. Bosek, A. Dudek, M. Farnik, J. Grytczuk, P. Mazur. Hat chromatic number of graphs. Discrete Mathematics. 344(12). 1127620. (2021).