Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

Título: Subfall coloring of graphs

Data: 05/07/2024
Horário: 10h00
Local: Online

Resumo:

Dado um grafo G, uma k-coloração (própria) de G é uma função f : V(G) →{1,…, k} tal que f(u) ≠ f(v) para toda aresta uv ∈ E(G). Dada uma k-coloração f de um grafo G, um vértice u ∈ V(G) é dito b-vértice com respeito à f se para toda cor i ∈ {1,…, k} − { f(u)} existe pelo menos um vértice v ∈ V(G) tal que f(v) =  i e uv ∈ E(G). Uma k-coloração f de um grafo G é chamada de fall k-coloração se todo vértice u ∈ V(G) é b-vértice com respeito à f; e o número fall acromático, denotado por ψ f (G), é o maior inteiro positivo k tal que o grafo G admite uma fall k-coloração. Dado um grafo G e um inteiro k, uma subfall k-coloração de G é uma fall k-coloração de algum subgrafo induzido H ⊆ G; e o número subfall acromático, denotado por ψ fs (G), é o maior inteiro positivo k tal que G admite uma subfall k-coloração. Nesse trabalho preliminar apresentamos uma revisão dos resultados sobre fall k-coloração encontrados na literatura, que são os resultados mais relacionados à subfall coloração. Além disso, provamos que o problema de decidir se um grafo G admite uma subfall k-coloração é NP-completo para todo inteiro k ≥ 4, respondendo a uma pergunta levantada em (DUNBAR et al., 2000). Apresentamos também um algoritmo FPT de programação dinâmica para decidir se um grafo G admite subfall k-coloração quando parametrizado pela sua largura em árvore tw(G), com k ≥ 3. Ademais, dado um grafo G, estabelecemos a continuidade do parâmetro ψ fs (G) e a sua relação com alguns parâmetros relacionados, sendo eles o número b-cromático b(G) e o número de Grundy Γ(G). Finalmente, definimos o índice subfall cromático de um grafo G e estabelecemos uma versão do teorema de Vizing para o mesmo em grafos planares e periplanares. Apresentamos também um Plano de Atividades para os próximos meses do curso de mestrado.

Banca examinadora:

• Prof. Dr. Júlio César Silva Araújo (MDCC/UFC – Orientador)
• Prof.ª Dr.ª Ana Shirley Ferreira da Silva (UniFI/Itália – Coorientadora)
• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC)