|
图的染色问题是图论研究中一个活跃的领域,因此各类染色问题被相继提出并加以发展应用,赖宏建等人在2006年提出了条件染色.图的标号问题就是图的染色问题的推广,其理论研究背景是频道分配问题.Griggs和Yeh在1992年提出了L（2,1）－标号问题,作为标号问题的另一种推广,孙磊老师于2008年提出了邻域限制标号问题.条件染色是传统的点染色在理论上的自然地推广,是在文献[2]中首次提出的.对于整数k＞0和r＞0,图G的一个正常（k,r）－染色是一个满足下面两个条件的映射c:V（G）→{1,2…k},（1）若uv∈E（G）,则c（u）≠c（v）;（2）对任意的v∈V（G）,|c（NG（v））|≥min{|NG（v）|,r}.对于固定的r,使G有—个正常的（k,r）－染色的最小的k是图G的第r个条件色数,记为Xr（G）.由条件色数的定义很显然的得到X1（G）＝X（G）.作为频率设置问题的一个变形, Griggs和Yeh在1992年提出了L（2,1）－标号问题.图G的一个L（2,1）－标号是一个满足下面两个条件的映射c:V（G）→{0,1,2…k},（1）对任意的u,v∈V（G）,若d（u,v）＝1,则|c（u）－c（v）|≥2;（2）对任意的u,v∈V（G）,若d（u,v）＝2,则|c（u）－c（v）|≥1.当所有的标号都小于等于k时,称图G有一个k－L（2,1）－标号.则使得图G有一个k－L（2,1）－标号的最小的正整数k称为图G的L（2,1）－标号数,记为λ（G）.令c是图G的一个的λ（G）－L（2,1）－标号.令c-1（i）＝{v∈V（G）|c（v）＝i}.且令|c-1（i）|表示c-1（i）的基数.若对于一个整数h（0＜h＜k）满足|c-1（h）|＝0,则称h为c的一个洞.图G的洞数,记为ρ（G）,是图G的所有λ（G）－L（2,1）－标号中最少的洞的个数.对于一个整数k＞0,图G的一个k－L1,2－标号是一个满足下面两个条件的映射c:V（G）→{0,1,2…k},（1）任意的u,v∈V（G）,若d（u,v）＝1,则|c（u）－c（v）|≥1;（2）任意的u,v∈V（G）,若存在w∈V（G）,使得u,v∈NG（w）,则|c（u）－c（v）|≥2.则使得图G有一个k－L1,2－标号的最小的正整数k称为图G的邻域限制标号数,记为L1,2（G）.令c是图G的一个的k－L1,2－标号.令c-1（i）＝{v∈V（G）|c（v）＝i}且令|c-1（i）|表示c-1（i）的基数.若对于一个整数h（0＜h＜k）满足|c-1（h）|＝0,则称h为c的一个洞.本文中Δ（G）表示图G的最大度,δ（G）表示图G的最小度,d（u,v）表示u,v两点在图G中的距离,NG（v）表示v在图G中的邻域.在本文的第二章我们主要得到了以下结论.引理2.1.1图G是任意简单图,则L1,2（G）≥2（Δ（G）－1）.引理2.1.2图G是任意简单图,且L1,2（G）＝2（Δ（G）－1）.则任意的最大度点v,c（v）≡1（mod2）,且任意的u∈NG（v）,c（u）＝2i（i＝0,1,2…Δ（G）－1）.定理2.1.3若图G中有两个最大度点相邻,则L1,2（G）≥2Δ（G）－1.定理2.1.4若正则图G中有奇圈且Δ≥4,则L1,2（G）≥2Δ（G）.定理2.1.5图G是圈,则当|V（G）|≡0（mod4）时,L1,2（G）＝3;否则,L1,2（G）＝4.定理2.1.6设图G是k－退化图,Δ≥4且无三角,则2（Δ－1）≤L1,2（G）≤Δ（6k－3）＋k－3k2.定理2.2.1设图G是树,Δ（G）≥3,且图G中有两个最大度点相邻,则L1,2（G）＝2Δ（G）－1.定理2.2.3设图G是树,Δ（G）≥3,若图G中无最大度点相邻且任意两个最大度点的距离为偶数,则L1,2（G）＝2（Δ（G）－1）.定理2.2.4设图G是树,Δ（G）≥4,若存在一条包含所有最大度点的路.则当图G中无两个最大度点不相邻且存在两个最大度点的距离为奇数时,L1,2（G）＝2（Δ（G）－1）.定理2.2.5设图G是树,Δ（G）≥3,若图G中只有一个最大度点,则L1,2（G）＝2（Δ（G）－1）.我们证明了当c是G的一个最小的邻域限制标号,且h是c的一个洞,图G具有的下述性质.性质2.3.1图G是任意简单图,若c是G的一个最小的邻域限制标号,且h是c的一个洞,则h－1,h＋1都不是c的洞.性质2.3.2令c是G的一个最小的邻域限制标号,h是c的一个洞.若|c-1（h－1）|≥2或|c-1（h＋1）|≥2且c（u）＝h－1,c（v）＝h＋1,则肯定存在一点x满足d（u,x）≤2且c（x）＝h＋1或一点y满足d（v,y）≤2且c（y）＝h－1.性质2.3.3图G是任意简单图且无三角,令c是图G的一个最小的邻域限制标号,且h是c的一个洞.若对任意的标号i,满足|c-1（i）|≥2,则若c（v）＝h－1或h＋1,则肯定存在两点v1,v2满足d（v,v1）＝1,d（v,v2）＝2,c（v1）＝c（v2）＝h＋1或h－1且v2（?）NG（v1）.性质2.3.4图G是任意简单图且无三角,令c是G的一个最小的邻域限制标号,且h是c的一个洞.若存在路uv0v,满足c（u）＝h－1,c（u）＝h＋1且任意的x满足d（u,x）＝2,但c（x）≠h＋1且任意的y可满足d（v,y）＝2,但c（y）≠h－1.则此时|c-1（c（v0））|＝1.性质2.3.5图G是任意简单图且无三角,令c是G的一个最小的邻域限制标号, h是c的一个洞,且|c-1（h－1）|＝1,|c-1（h＋1）|≥2.若令c（u）＝h－1,则对任意的vi满足c（vi）＝h＋1,存在路uwivi.若任意的vi满足d（u,vi）≠1,则|c-1（c（wi））|＝1.或有且仅有一个vi满足d（u,vi）≠1.G是一个简单图,V（G）＝{v1,v2,…,vn},G[I2]的点集和边集如下定义:V（G[I2]）＝{v1,v2,…,vn,v1’,v2’,…,vn’},E（G[I2]）＝E（G）∪{vi’vj’,vi’vj|vivj∈E（G）},则G[I2]称为G的点分裂图.令G＝（V（G）,E（G））,V（G）＝{v1,v2,v3,…vn},M－构造图M（G）的点集和边集是如下定义的, V（M（G））＝{v1,…vn,u1,…un,v},E（M（G））＝{uiv|i＝1,2…n}∪{uivj|vivj∈E（G）}.M－构造图在研究图染色问题的临界性上有重要应用.在本文的第三章我们讨论了图G与其分裂图G[I2]的条件色数的关系及图G与其M－构造图M（G）的条件色数的关系,给出了几类特殊图的条件色数.定理3.1.1图G与其分裂图G[I2]的条件色数的关系如下,定理3.2.1若整数r满足0＜r≤2Δ（G）,则任意的图G的M－构造图M（G）满足Xr（M（G））≥r＋2.定理3.2.2图G与M－构造图M（G）的条件色数的关系如下:对任意的正整数k和m,G（k,m）表示一些图的集合.若G∈G（k,m）当且仅当V（G）＝V0∪V1∪…Vm,|V0|＝|V1|＝…|Vm|＝k且对任意的0≤i≤m,G（Vi）的导出子图是一个空图;对任意的0≤i＜j≤m,G[Vi∪Vj]的导出子图是一个完美匹配.在本文的第四章我们主要研究G（k,m）这类图的L（2,1）－标号问题并得到了以下结论.定理4.1 k≥3,n≥2,若图G∈G（k,n＋1）且包含一个子图H∈G（k,n）使得λ（H）＝2n且ρ（H）＝n,则λ（G）＝2（n＋1）.定理4.2 k≥3,若G∈G（k,2）,则λ（G）＝4且ρ（G）＝0或2.定理4.3若G∈G（3,3）,则λ（G）＝6.定理4.4若G∈G（4,3）,则λ（G）＝6.
|