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

Título: (Sub)Fall coloring of graphs

Data: 06/09/2024
Horário: 14h00
Local:  Sala de Reuniões – Bloco 910

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 a 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 a f. Se um grafo G admite uma fall k-coloração para algum inteiro positivo k, 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 positivo 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. Nesta dissertação apresentamos uma breve 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 como sendo o parâmetro correspondente para coloração de arestas e estabelecemos uma versão do Teorema de Vizing para o mesmo em grafos planares e periplanares.

Banca examinadora: