Circular backbone coloring for graphs without cycles of size four

Abstract

Given a graph G = (V(G),E(G)) and a subgraph H = (V(H),E(H)) of G, a q-backbone k-coloring of (G,H) is a function φ : V(G) → { 1 , 2 , 3 ,...,k} such that, for every edge uv ∈ E(G) , we have |φ(u) − φ(v)| ≥ 1 and, for every edge uv ∈ E(H) , we have |φ(u) − φ(v)| ≥ q. The q-backbone chromatic number of (G,H) , denoted by BBCq (G,H) , is the smallest integer k such that there exists such coloring φ . Similarly, a circular q-backbone k-coloring of (G,H) is a function φ : V(G) → { 1 , 2 , 3 ,...,k} such that, for every edge uv ∈ E(G) , we have |φ(u) − φ(v)| ≥ 1 and, for every edge uv ∈ E(H) , we have k − q ≥ |φ(u) − φ(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 φ . In this dissertation, we firstly present a brief summary on the results found in literature regarding Backbone Coloring. Then, we prove that if G is a planar graph without cycles of size four and F is a spanning forest of induced paths of G, then CBC2 (G,F) ≤ 7. Lastly, we show the following theorem : if G is a connected graph and k ≥ max {χ(G), χ(G)/ 2 +q} , then there exists a proper k-coloring c of G such that Gc,q is connected, where Gc,q is the subgraph of G such that V(Gc,q ) = V(G) and E(Gc,q ) is the set of edges vw ∈ E(G) that satisfy |c(v)−c(w)| ≥ q.