文献综述
研究价值：在无线电通信波段分配的促动下，有了图的距离2着色这一迷人的推广概念。
古典的点着色问题中，仅对相邻点限制条件，即相邻点着色不同；图的距离2着色则要求更强的条件-- 给定图中相邻点着色及距离2的两点着色都限制条件。因为无线电通信波段分配问题中，要求使每个发射台分配的波段相互无干扰且波段有效利用。为达此目的，须考虑“直接干扰”-- 任两个“非常近”的发射台之间的干扰，及“间接干扰”—任两个“近”的发射台之间的干扰。转化成图论问题：图的顶点代表发射台，有边代表有干扰，点的着色相应于发射台的频率，这样就有了推广的图着色概念。
定义：给定一个图G及两个非负整数h,k，L(h,k)-着色是指相邻点色差不小于h且距离2 的两个点的色差不小于k的G的非负整数点着色。最大色与最小色之间的差称为跨度，所有L(h,k)-着色对应的跨度中最小的称为最小跨度，记之为lambda;h,k(G),称之为图G的lambda;h,k-数. 这一概念最初由Griggs和Yeh以h=2,k=1的特殊情形首先提出,在此之前,Robort把h=1,k=1情形作为组合分配问题已研究过.
对于图的距离2标号，有一个很有趣的问题，那就是图的关联图的距离2 标号问题，也即图的(d,1)-全标号问题。1995年，Whittlesty、Georges 和Mauro首先研究了图G的关联图的L(2,1)-标号。2002年，Havet和Yu称图G的关联图的L(2,1)-标号为图G的(2,1)-全标号，同时将之推广得(d,1)-全标号概念。（(1,1)-全标号即全着色)。Havet和Yu 在研究了(d,1)-全标号数的一般规律，给出了(d,1)-全标号数的一个上界，同时提出一个关于 (d,1) -全标号数上界的猜想----Havet-Yu猜想：lambda;dTle;Delta; 2d-1，并分情形、限图类具体研究猜想的正确性。
图的全标号问题即研究图的关联图的距离2 标号问题。图的关联图可看成图的边-路P3替换图。文献[12-13]对(d,1)-全标号的推广问题——图的边-路替换图的L(d,1)-标号问题进行了研究。
本课题将讨论某些积图的局部边路替换图的L(1,1)-标号问题。
总之，图的距离2着色问题是无线电通信波段分配问题的图论模式，有着很大的探讨空间，它的研究成果对波段分配问题起着推进作用。
参考文献:
[1] J.R.Griggs and R.K.Yeh, Labeling graphs with a condition at distance 2[J].SIAM J.Disc.Math, 1992,5:586-595
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
