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

设H为G的一个生成子图,(G,H)的一个BB-k染色是指一个映射f:V(G)→{1,2…,k},满足以下两条:(i)|f(u)-f(u)|≥1,uu∈E(G)\E(H).(ii)|f(u)-f(u)|≥2,uv∈E(H).定义(G,H)的BB-色数xb(G,H)为最小的整数k,使得(G,H)是BB-k可染的.本文证明了...

Backbone coloring for C_4-free planar graphs

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.