没有4-圈的平面图的BB-染色

Backbone coloring for C_4-free planar graphs

设H为G的一个生成子图,(G,H)的一个BB-k染色是指一个映射f:V(G)→{1,2,...,k},满足以下两条:(i)|f(u)-f(v)|1,uv∈E(G).(ii)|f(u)-f(v)|2,uv∈E(H).定义(G,H)的BB-色数χb(G,H)为最小的整数k,使得(G,H)是BB-k可染的.本文证明了对于任意的连通平面图G,若G没有4-圈,则存在G的一棵生成树T,使得χb(G,T)4.

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.