Título: Jogos de Perseguição em Grafos e Coloração Localmente Identificável.

Data: 05/05/2017 Horário: 13h Local: Sala de Seminários do Bloco 952 - Campus do Pici

Resumo:

Nesta tese estudamos os problemas de coloração localmente identificável (lid-coloração) e diversos parâmetros relacionados a jogos de perseguição em grafos. Para colorações localmente identificáveis, mostramos que o número lid-cromático e o número lid-cromático forte são ambos $O(n^{\frac{1}{2}-\varepsilon})$-inaproximáveis em tempo polinomial, a menos que $P=NP$, bem como algoritmos lineares para $(q,q-4)$-grafos e para grafos com largura em árvore limitada para ambos os parâmetros. Com relação a jogos de perseguição, estudamos dois jogos diferentes: Jogo de Polícia e Ladrão e o Jogo do Espião. Para o Jogo de Polícia e Ladrão mostramos valores exatos para o cop-number e o $k$-capture time de grafos $P_4$-tidy. Além disso mostramos que a famosa conjectura de Meyniel é válida para grafos $P_4$-tidy conexos e $(q,q-4)$-grafos conexos com pelo menos de $q^2$ vértices. O Jogo do Espião foi introduzido recentemente por N. Nisse. Mostramos que esse problema é NP-difícil para qualquer velocidade $s\geq 2$ do espião e qualquer distância $d\geq0$ para os guardas e, além disso, $(1-o(1)) \ln n$-inaproximável em tempo polinomial, a menos que $P=NP$. Ademais, mostramos limites superiores para um dos parâmetros do jogo para ciclos e caminhos e provamos que a versão direcionada do problema é PSPACE-difícil para DAG's.

Banca:

• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC - Orientador)
• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC)
• Prof. Dr. Ronan Pardo Soares (UFC)