Jogos de perseguição em grafos e coloração localmente identificável

Abstract

On this thesis we study the locally identifying coloring of graphs (lid-coloring) and many parameters related to pursuit games on graphs. For locally identifying colorings, we show that the lid-chromatic number and the strong lid-chromatic number are both O(n^(1−E))-inapproximable in polynomial time, unless P = NP. We also show linear algorithms for (q; q − 4)-graphs and for graphs with bounded treewidth for both parameters. Regarding pursuit games, we study two distinct games: The Cops and Robber and the Spy-Game. For the Cops and Robber game we show exact vallues for the cop-number and the k-capture time of P4-tidy graphs and (q, q − 4)-graphs. Furthermore we show that the famous Mayniel conjecture is true for P4-tidy graphs and (q, q − 4)-graphs with at least q vertices. Regarding the Spy-Game we show that it is NP-hard for any speed s and any distance d and, besides that, it is (1 − o(1)) ln n-inapproximable in polynomial time, unless P = NP. Furthermore, we show bounds to the number of guards needed to win the game when it is played on paths and cycles. We also prove that the directed version of the game is PSPACE-hard for DAG’s.