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

Título: Coloração backbone em grafos: revisão bibliográfica e introdução de uma versão direcionada

Data: 06/12/2024
Horário: 10h
Local: Sala de Seminários – Bloco 952

Resumo:

Dado um inteiro $q \ge 2$, um grafo $G$ e um subgrafo gerador $H$ de $G$, chamado de \emph{backbone} de $G$, definimos uma $k$-coloração $q$-\emph{backbone} de $(G,H)$ como sendo uma $k$-coloração própria $c$ de $G$ tal que, para todo $uv \in E(H)$, a seguinte condição é satisfeita: $|c(u)-c(v)| \geq q$. Neste trabalho, apresentamos uma revisão bibliográfica que aborda resultados gerais sobre um parâmetro crucial relacionado a essa coloração, conhecido como número cromático $q$-\emph{backbone}, denotado por $\bbc_q(G,H)$. O número cromático $q$-\emph{backbone} é o menor inteiro $k$ tal que existe uma $k$-coloração $q$-\emph{backbone} de $(G,H)$. Adicionalmente, apresentamos nossas contribuições para essa coloração e introduzimos uma variação direcionada, denominada Coloração \emph{Backbone} Direcionada. Também discutimos os resultados iniciais referentes ao seu número cromático correspondente.

Banca examinadora:

• Prof. Dr. Júlio César Silva Araújo (MDCC/UFC) – Orientador
• Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC)
• Prof. Dr. Atílio Gomes Luiz (UFC/Quixadá)