Backbone coloring for C_4-free planar graphs
Bu Yue · Scientia Sinica Mathematica · 2011
Let G be a graph and H a spanning subgraph of G.A backbone-k-coloring of (G,H) is a mapping f : V (G) → {1,2,...,k} such that |f(u)-f(v)| 2 if uv ∈ E(H) and |f(u)-f(v)| 1 if uv ∈ E(G)\E(H).The backbone chromatic number of (G,H),denoted by χb(G,H),is the smallest integer k such that (G,H) has a backbone-k-coloring.In this paper,we prove that if G is a connected C4-free planar graph,then there exists a spanning tree T of G such that χb(G,T) 4.