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

Abstract

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.