图的染色问题是图论研究中的重要问题和热点问题之一,标号问题是染色问题的推广,它起源于通讯问题中的信道频率分配问题.1991年,Roberts提出了给相近和非常相近的发射机分配不同的信道,并且非常相近的发射机接收的信道频率要至少相差两个单位.受这一问题的启发,Griggs和Yeh在1992年系统地提出了 L(2,1)-标号问题.这一概念后来被推广到了图的L(p,q)-标号问题.令p,g为正整数,图G的一个k-L(p,q)-标号是指映射f:V(G)→ {0,1,2,…,k},使得对任意的2个顶点u和,若d(u,v)=1,则有 |f(u)-f(v)|≥p,若d(u,v)=2,则有 |f(v)-f(v)|≥q.其最小的 k值称为图 G 的L(p,g)-标号数,记为λp,q(G).图的L(1,1)-标号等价于2-距离染色.2001年,Montgomery在他的博士论文中提出了动态染色.令k,r为正整数,[k]={1,2,..…,k},图G的一个r-动态染色是指一个正常k-顶点染色f,满足对任意的顶点v,都有|f(NG(v))|≥min{d_G(v),r}.其最小的k值称为图G的r-动态色数,记作(?)(G).特别地,当r=△(G)时,r-动态染色就是图的2-距离染色.本学位论文研究与信道频率分配相关的特殊图类的L(2,1)-标号问题和r-动态染色问题.第一章综述了国内外关于L(2,1)-标号问题和r-动态染色问题的研究现状.第二章围绕Griggs-Yeh猜想展开研究.1992年,Griggs和Yeh猜想:对最大度△ ≥ 2的图G,有λ2.1(G)≤△~2.结合权转移方法和零点定理,我们得到了不含某些特殊短圈的平面图的列表L(2,1)-标号数的上界和平面图在最大度和围长限制条件下的列表L(2,1)-标号数的上界.论文的后面三章围绕赖虹建等人提出的关于平面图r-动态染色的猜想展开研究.2014年,类似Wegner猜想,赖虹建等人提出:对平面图G,若1 ≤ r ≤ 2,则(?)(G)≤r+3;若 3 ≤ r ≤7,则 Xrd(G)≤ r+5;若 r ≥ 8,则 (?)(G)≤[3r/2]+1.第三章研究了不含特殊短圈的平面图的列表2-距离染色数(即列表△-动态染色数)和平面图的2-距离染色数(即△-动态染色数),得到了:(1)不含4-圈和6-圈的平面图的列表2-距离染色数的上界;(2)平面图G的2-距离染色数的上界,这一结果改进了目前关于最大度△≤7的平面图的2-距离染色数的最好上界.第四章研究了围长至少为5和围长至少为7的平面图的(列表)r-动态染色数.证明了:(1)若G是g(G)≥ 5的平面图且r ≥ 15,则ch(?)(G)≤r+5;(2)若G是g(G)≥ 7的平面图且r ≥ 16,则(?)(G)≤ r+1.第五章研究了稀疏图的列表r-动态染色,给出了稀疏图的列表r-动态染色数至多为r+1的一些充分条件.证明了对满足下列情形之一的图G,有ch(?)(G)≤ r+1:(1)mad(G)<18/7且 r≥ 8;(2)mad(G)<5/2 且 r≥ 6;(3)mad(G)<12/5且 r ≥5;(4)mad(G)<2.8-ε 且 r ≥f(ε)=16/5ε-2,其中 0<ε≤1/10.