Backbone coloring of planar graphs for C8C8-free or C9C9-free

• In this paper, we study the problem of backbone coloring of connected planar graphs without 8-cycles and 9-cycles.
• In this paper, we are using the discharging technique to prove the Theorem.
• The result generalize the sufficient condition for the planar graphs of BB-4-colorable.

Let G=(V,E)G=(V,E) be a graph and H be a spanning subgraph of G. A backbone-k  -coloring of (G,H)(G,H) is a mapping φ  : V(G)→{1,2,⋅⋅⋅,k}V(G)→{1,2,⋅⋅⋅,k} such that |φ(u)−φ(v)|≥2|φ(u)−φ(v)|≥2 if uv∈E(H)uv∈E(H) and |φ(u)−φ(v)|≥1|φ(u)−φ(v)|≥1 if uv∈E(G)\E(H)uv∈E(G)\E(H). The backbone chromatic number of (G,H)(G,H) is the smallest integer k   such that (G,H)(G,H) has a backbone-k  -coloring, denoted by χb(G,H)χb(G,H). In this paper, we prove that if G   is a connected planar graph that is C8C8-free or C9C9-free and without adjacent 4-cycles, then there exists a spanning tree T of G   such that χb(G,T)≤4χb(G,T)≤4.