论文部分内容阅读
一个有序对G=(V,E)称为一个无向图,其中V是一个有限集合,E是V中的不同元素的无序对的集合.V中的元素叫做图G的顶点,E中的元素叫做图G的边.通常用V(G),E(G)分别表示图G的顶点集合与边集合.没有重边和环的图叫做简单图.
图G的一个正常k顶点染色是指一个映射φ:V→{1,…,k),使得对任意uv∈E(G),满足φ(u)≠φ(v).若图G有一个正常k点染色,那么就称图G是k点可染色的.图G的色数是指G有一个正常k顶点染色的数k的最小值,用x(G)表示.
令H是G的生成子图,(G,H)的一个BBC-k-染色是一个映射f:V(G)→{1,2,…,k),满足(1)若uv∈E(H),则｜f(u)-f(v)｜≥2；(2)若uv∈E(G)＼E(H),则｜f(u)-f(v)｜≥1.(G,H)的BBC-染色数就是指最小的整数k,使得(G,H)有BBC-k-染色,记作xb(G,H)=k.
近年来,图的染色概念不断演化,出现了很多与频率分配相关的染色如:L(2,1)-标号染色,距离2-染色,Radio-染色等概念.BBC-染色概念最早由HajoBroersma教授在第29届国际计算机方面的图理论研讨会议上提出的.它是一种与网络频率分配问题相关的图的染色问题.到目前为止,已经做出了不少结果.
已经证明了当图G的生成子图H分别是一棵生成树、一条Hamilton路、一个完美匹配或者一些不相交的独立星图时,(G,H)的BBC-染色数上界与图的正常顶点染色的关系.并证明了当G=TUC为Halin图,且G以生成树T为生成子图时,(G,T)的BBC-染色数.
本文主要讨论一些具体图类的BBC染色问题.在第二章中主要讨论对于图G的Mycielski图M(G),研究xb(G,TG)与xb(M(G),T′)之间的关系以及Xb(G,TG)与xb(M(G),T″)之间的关系,其中TG为G的生成树,T,T″分别为M(G)的两类特殊生成树.第三章中主要讨论了当图G为广义Petersen图G(n,k),且G(n,k)的生成子图是一棵生成树T0时,G(n,k)关于T0的BBC-染色数,即xb(C(n,k),T0)的值.以及当G(n,k)的生成子图是完美匹配M时,G(n,k)关于M的BBC-染色数,即xb(G(n,k),M)的值.