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

摘要

设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.