论文部分内容阅读
本文主要研究了平面图的两类染色问题:列表点染色和列表全染色。 设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-列表点可染色的。