平面图列表染色的一些结果

来源 :南京师范大学 | 被引量 : 0次 | 上传用户:loveag
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究了平面图的两类染色问题:列表点染色和列表全染色。  设c:E(G)∪V(G)→{1,2,…k}是从G的边集和顶点集构成的集合E(G)∪ V(G)到自然数集的一个映射,如果对任意相邻或相关联的两个元素x,y∈E(G)∪ V(G)均有c(x)≠c(y),则称c是G的一个正常全染色。  列表全染色是全染色的推广,这种染色对于图G的顶点和边可选用的颜色有一定的限制.对任意x∈V(G)UE(G),令L(x)为x的一个可用颜色集合,我们记L={L(x)∣ x∈V(G)∪ E(G)},称L为G的一个全列表指派.设L是图G的一个全列表指派.若存在G的一个全染色(ψ)对每一个x∈V(G)∪ E(G)都满足(ψ)(x)∈L(x),则称G是L-全可染色的.设k是一个正整数.如果对于图G的任意给定的全列表指派L当|L(x)|≥k对每一个x∈V(G)∪ E(G)都成立时,G都是L-全可染色的,则称G是k-列表全可染色的.列表全染色数是使得图G是列表全可染的最小的k即xi(G)=min{k|G是k-列表全可染色的}。  在第二章我们针对于最大度为5的平面图做了一些研究,具体的得到如下结论:设G是一个最大度为5的平面图。  (1)G是9-列表全可染色的。  (2)G中不含5-圈时,G是8-列表全可染色的。  (3)G不含5-圈,并且每个最大度点最多邻接两个3-面时,G是7-列表全可染色的。  (4)G中不含C4,C5,C7,C8时,G是6-列表全可染色的。  (5)G的最大的平均度mad(G)<20/7时,G是6-列表全可染色的。另一种我们所关注的染色是列表点染色问题。  图G的一个点染色是从顶点集合V(G)到颜色集合S的一个映射c,其中S中的元素称为颜色,染相同颜色的顶点构成一个色类.如果|S|=k,则称c为图G的一个k染色,通常.S={1,2…,k).图G的正常k-染色是将k种颜色分配给其顶点集V(G),使得相邻的顶点的颜色不同.图G的色数记为x(G),x(G)=min{k| G有正常的k-染色}。  列表点染色是顶点染色的一个推广,这种染色对于图G的每个顶点可选用的颜色有一定的限制.图G的列表分派L是指给图G每个顶点v一个颜色集合L(v).给定图G的列表分派L,如果图G存在一个正常染色Φ使得每个顶点所染的颜色均选自各自的颜色集合L(v),则称G是L-点可染色的.设k是一个正整数.如果对于图G的任意给定的列表指派L,当|L(x)|≥k对每一个x∈V(G)都成立时,G都是L-点可染色的,则称G是k-列表点可染色的.列表点染色数指的是使得图G是列表点可染的最小的k,即x1(G)=min{k| G是k-列表点可染色的)。  第三章中我们对3-列表点染色的充分条件做了深入研究,得到了如下的结论:  (1)不含{4,6,7,8)-圈且三角形的距离至少为2的平面图是3-列表点可染色的。  (2)不含{4,5,7)-圈且三角形的距离至少为2的平面图是3-列表点可染色的。
其他文献
本文主要对椭圆、抛物型方程的系数反演问题进行了研究,这两类反问题不论在金融、物理、医学、地质探测和无线电传播领域还是在电磁金属成型技术中都有着极其广泛的应用。文章
多个体系统理论是控制理论的一个比较新的研究方向.它的研究对象是按照一定的网络结构连接起来的多个动态子系统的全体,其中每一个子系统又常常称为一个个体,个体之间通过连接
本文主要的研究的对象一类奇异偏微分方程,其中方程的奇异项形如:-x{u≥0}μ|▽u|(l)/um.不难看到,这一项在u=0的点可能产生奇异性.又由于这一项的奇异性依赖于梯度(也被称作低
学位
正系统是一类在几乎所有的科技领域中都会见到的系统,如工程学,生态学,经济学,生物医学及社会科学等.正系统的一个公共特征是在非负的初始状态与输入下,系统的状态及输出也限制为
编码理论在通信中起着重要的作用,码的各方面性质备受各个专家的关注.结合方案是伴随与部分平衡不完全区组设计的一个组合结构,它与编码理论、图论、有限域有着密切联系,特别