Backbone Coloring of Graphs with Galaxy Backbones

A (proper) k-coloring of a graph G = (V,E) is a function c : V (G) → {1,...,k} such that c(u) ≠ c(v) for every uv ∈ E(G). Given a graph G and a subgraph H of G, a q-backbone k-coloring of (G,H) is a k-coloring c of G such that q ≤ |c(u) − c(v)| for every edge uv ∈ E(H). The q-backbone chromatic number of (G,H), denoted by BBCq(G,H), is the minimum integer k for which there exists a q-backbone k-coloring of (G,H). Similarly, a circular q-backbone k-coloring of (G,H) is a function c: V (G) → {1,...,k} such that, for every edge uv ∈ E(G), we have |c(u)−c(v)| ≥ 1 and, for every edge uv ∈ E(H), we have k−q ≥ |c(u)−c(v)| ≥ q. The circular q-backbone chromatic number of (G,H), denoted by CBCq(G,H), is the smallest integer k such that there exists such coloring c. In this work, we first prove that if G is a 3-chromatic graph and F is a galaxy, then CBCq(G,F) ≤ 2q + 2. Then, we prove that CBC3(G,M) ≤ 7 and CBCq(G,M) ≤ 2q, for every q ≥ 4, whenever M is a matching of a planar graph G. Moreover, we argue that both bounds are tight. Such bounds partially answer open questions in the literature. We also prove that one can compute BBC2(G,M) in polynomial time, whenever G is an outerplanar graph with a matching backbone M. Finally, we show a mistake in a proof that BBC2(G,M) ≤ Δ(G)+1, for any matching M of an arbitrary graph G [Miskuf et al., 2010] and we present how to fix it.