Resultados em jogos de coloração e perseguição em grafos

Abstract

In this thesis we study three games in graphs. In the graph coloring game we answer a long-standing open question proposed by Bodlaender in 1991: the game chromatic number is PSPACE-hard. In the greedy coloring game we also prove that the game Grundy number is PSPACE-hard. In fact, we prove that both problems, the graph coloring game and the greedy coloring game, are PSPACE-Complete even if the number of colors is the chromatic number. Moreover, we prove that the game Grundy number is equal to the chromatic number for several superclasses of cographs, extending a result of Havet and Zhu in 2013. In the spy game we obtain an upper bound on the strong product of two general graphs and obtain examples of King grids that match this bound and other examples for which the guard number is smaller. We also obtain the exact value of the guard number in the lexicographic product of two general graphs for any distance d ≥ 2. From the algorithmic point of view, we prove a positive result: if the number k of guards is fixed, the spy game is solvable in polynomial time O(n3k+2) for every speed s ≥ 2 and distance d ≥ 0. In other words, the spy game is XP when parameterized by the number of guards. This XP algorithm is used to obtain an FPT algorithm on graphs with few P4’s. As a negative result, we prove that the spy game is W[2]-hard even in bipartite graphs when parameterized by the number of guards, for every speed s ≥ 2 and distance d ≥ 0, extending the hardness result of Cohen et al. in 2018.