1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2018/2019
4. Mathematics - PhD studies
5. Gry na grafach

Generate PDF for this page

Gry na grafach - course description

Aim of the course

Omówienie znanych gier na grafach oraz parametrów grafowym związanymi z tymi grami. Przedstawienie metod dowodzenia twierdzeń podających ograniczenia na parametry grafowe związane z grami. Zapoznanie doktorantów z otwartymi problemami związanymi z omawianymi zagadnieniami.

Prerequisites

Save changes

Zaliczona na poziomie studiów I stopnia: matematyka dyskretna.

Scope

Rozgrywane kolorowanie wierzchołków grafu, złożoność problemu rozgrywana liczba chromatyczna drzew, grafów zewnętrznie planarnych, planarnych. Podstawowe problemy otwarte związane z ta grą.

Rozrywana liczba kolorowalności a rozgrywana liczba chromatyczna grafu. Liczba kolorowalności częściowych k-drzew.

Uogólnienia i różne modyfikacje rozgrywanego kolorowania wierzchołków grafów. Defekt rozgrywanego kolorowania grafu.

Rozgrywane kolorowanie krawędzi drzew i grafów k-zdegenerowanych. Rozgrywane kolorowanie incydencji grafu.

Rozgrywana wybieralność i barwność grafu oraz wiązek między tymi parametrami.

Rozgrywana liczba i indeks Grundy.

Gry dominujące.

Gry typu Cops-Robbers.

Gry na digrafach, gry typu Nim.

Teaching methods

Wykład: konwencjonalny.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Forma zaliczenia przedmiotu – egzamin.

Ocena końcowa przedmiotu: ocena z egzaminu

Warunkiem zaliczenia egzaminu jest uzyskanie pozytywnej oceny ostatecznej z egzaminu.

Recommended reading

1. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
2. H. L. Bodlaender, On the complexity of some colouring games, Internat. J. Found. Comput. Sci. 2 (1991) 133-148.
3. A. Bonato, R. J. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Society, 2011.
4. J.A. Bondy U.S.R. Murty, Graph Theory, Springer, 2008.
5. U. Faigle, U. Kern, H.A. Kierstead, W.T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993) 143-150.
6. H. A. Kierstead, A simple competitive graph colouring algorithm, J. Combin. Theory Ser. B 78 (2000) 57-68.

Further reading

1.  Wybrane artykuły z podanej tematyki.

Notes

Modified by dr Alina Szelecka (last modification: 14-07-2018 07:50)