图的哈密顿路骨架上的BB-染色

为了有效解决网络信息传输系统中的频道分配问题,在设计网络线路时,只对该网络线路中更重要的子结构(称为骨架)给出更多的限制,而对其他的部分作较少的限制,这类问题可抽象为图的BB-染色模型,它是经典染色理论的重要变体.利用圈平方图和广义Petersen图描述两类特殊的网络信息传输系统,采用哈密顿路径作为图的骨架,对圈平方图和广义Petersen图的λ-BB-染色展开研究,得到了BBC_(λ)(G,P)=λ+2.

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

研究了没有7-圈的连通平面图的BB-染色问题.应用经典的Discharging方法,证明了没有7-圈且不含相邻4-圈的连通平面图G,存在G的一棵生成树T,使得(G,T)是BB-4-可染的.这一结果进一步拓展了平面图的BB-4-可染的充分条件.

没有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色数x_b(G,H)为最小的整数k,使得(G,H)是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b(G,T)=4.

没有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.