The Backbone Coloring Of Graphs

Let V be a set of n(n> 0) elements. E be a set of by some binary subset of V. Call a pair G=(V, E) is a graph, the elements of V and E are the vertex and edge of G. The set V and E are the vertex set and edge set of G.Let G be a graph and H be a spanning subgraph of G. A backbone-k-coloring of (G, H) is a mapping φ:V(G)→{1,2,…,k} such that |φ(p(u)-φ(v)|> 2 if uv∈ E(H) and |φ(u)-φ(v)|> 1 if uv∈E(G)\E(H). The backbone chromatic number of (G, H) is denoted by Xb(G, H)=min{k|G is backbone-k-colorable}.A backbone-L-coloring of (G, H) is a backbone coloring c of (G, H), such that c(v)∈L(v) for every vertex v. We say (G, H) is backbone-L-colorable if there exists a backbone-L-coloring of (G,H). Furthermore, we say (G,H) is backbone-k-choosable if (G, H) is backbone-L-colorable for any list assignment L with|L(v)|> k for all v∈V(G). The backbone choice number of(G,H) is denoted by chBB(G,H)= min{k|(G,H)| is backbone-k-choosable}.On the backbone coloring of planar graphs, a lot of research has been made. In chapter 2, we show that if G is a connected planar graph and 3-cycles is not adjacent to 5-cycles, then there exists a spanning tree T of G such that χb(G, T)< 4. In chapter 3, we show that if G is C7-free or Cg-free or C9-free and without adjacent 4-cycles, then there exists a spanning tree T of G such that χb(G, T)< 4. The results generalize the sufficient condition for the planar graphs of BB-4-colorable by using the discharging technique.