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

摘要

设H为G的一个生成子图,(G,H)的一个BB-k-染色是指一个映射f:V(G)→{1,2,…,k},当uv∈E(H),|f(u)-f(v)|≥ 2;当uv∈E(G)＼E(H),|f(u)-f(v)|≥1.定义(G,H)的BB色数Xb(G,H)为最小的整数k,使得(G,H)是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得Xb(G,T)=4.