Backbone Coloring of Graphs with Galaxy Backbones
Camila Araujo, Júlio Aráujo, Ana Silva, Alexandre Cezar · Electronic Notes in Theoretical Computer Science · 2019
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 BBC q ( 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 CBC q ( 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 CBC q ( G , F ) ≤ 2 q + 2. Then, we prove that CBC3( G , M ) ≤ 7 and CBC q ( G , M ) ≤ 2 q , 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 [Miškuf et al. , 2010] and we present how to fix it.