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 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)| (q≤|c(u)−c(v)|≤k−q), for every edge uv∈E(H). The (circular) q-backbone chromatic number of (G,H), denoted by BBCq(G,H) (CBCq(G,H)), is the minimum integer k for which there exists a (circular) q-backbone k-coloring of (G,H). In this work, we (partially) answer three questions posed by Havet et al. (2014), namely, we prove that if G is a planar graph, H is a spanning subgraph of G and q is a positive integer, then: CBCq(G,H)≤2q+2 when q≥3 and H is a galaxy; CBCq(G,H)≤2q when q≥4 and H is a matching; and CBC3(G,H)≤7 when H is a matching and G has no triangles sharing an edge. In addition, we present a polynomial-time algorithm to determine both parameters for any pair (G,H), whenever G has bounded treewidth. Finally, we show how to fix a mistake in a proof that BBC2(G,M)≤Δ(G)+1, for any matching M of an arbitrary graph G (Miškuf et al., 2010).