Coloração Backbone em grafos: revisão bibliográfica e introdução de uma versão direcionada

• Ano de defesa: 2025
• Autor(a) principal: Castro, Rayane Gomes de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Coloração de grafos; Coloração backbone; Número cromático; Coloração backbone direcionada; Graph coloring; Backbone coloring; Chromatic number; Directed backbone coloring; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.ufc.br/handle/riufc/79719

Given an integer q ≥ 2, a graph G, and a spanning subgraph H of G, called the backbone of G, we define a q-backbone k-coloring of (G,H) as a proper k-coloring c of G such that, for every uv ∈ E(H), the following condition is satisfied: |c(u)−c(v)| ≥ q. In this work, we present a literature review that covers general results on a crucial parameter related to this coloring, known as the q-backbone chromatic number, denoted by BBCq(G,H). The q-backbone chromatic number is the smallest integer k such that there exists a q-backbone k-coloring of (G,H). Additionally, we present our contributions to this coloring and introduce a directed variation, called the Directed Backbone Coloring. We also discuss the results obtained regarding its corresponding chromatic number.