Um survey sobre resultados recentes em coloração backbone

Abstract

Let G=(E(G),V(G)) be a graph and H=(E(H),V(H)) be a subgraph of C, for any integers q and k, a q-backbone k-coloring of a pair (G,H) is a proper coloring c: V(G) → {1,2,3.,...k} such that for each uv, |c(u) −c(v)| ≥ q if uv belongs to E(H). The q-backbone chromatic number of (G,H), BBCq (G,H), is the smallest positive integer k such that the graph is q-backbone k-colorable. Given a graph G and a spanning subgraph H of G, a circular q-backbone k-coloring of (G,H) is a k-coloring c of G such that q ≤ |c(u)−c(v)| ≤ k−q for each edge uv ∈ E(H). The circular q-backbone chromatic number of (G,H), denoted by CBCq (G,H), is the smallest integer k for which there is a circular q-backbone k-coloring of (G,H). This paper proposes to present a survey where we organize researches in the Backbone coloring. Our main objective is to present recent results of BBC and CBC for different backbone structures.