论文部分内容阅读
Hajo Broersma教授在第29届国际计算机方而的图理论研讨会议上首次提出了BB-染色这个概念.这是一种与网络频率分配问题相关的图的染色模型.
把有序对G=(V, E)称为一个图，其中V是一个有限集合，E是V中的某些元素组成的无序对的集合.V中的元素叫做图G的顶点，E中的元素叫做图G的边.令H是G的一个生成子图，把映射f(∶)V(G)→{1，2，…，k}称为（G，H）的一个BB-k染色，满足(1)若vu∈E（H），则|f(u)-f(v)|≥2;(2)若uv∈E(G)E（H），则|f(u)-f(v)|≥1.使(G，H)有BB-染色的最小的正整数k称为（G，H）的BB-色数，记作BB(G，H)=k.
对于平面图的BB-染色，王维凡教授等人提出:用β表示最小的正整数k，使得对每个围长至少为k的非二部平面图G，存在一棵生成树T，使得BB(G，T)=4.确定β的值.由已有的结论我们知道β=4，对此，我们继续研究:对于可平面图G，存在一棵生成树T，使得BB(G，T)=4的充分条件.
对于上述问题，本文主要分以下几个部分来展开讨论.第二章主要讨论了对于没有6-圈或7-圈且任意两个三角形不相邻的平而图G，证明了G中存在一棵生成树T，使得BB(G，T)≤4.第三章中主要讨论了对于没有8-圈或者9-圈且任意两个三角形不相邻的平面图G，证明了G存在一棵生成树T，使得BB(G，T)≤4.