平面图的边—面染色和完备染色

《平面图的边—面染色和完备染色》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据平面图的边一面染色和完备染色Edge-facecoloringandentirecoloringofplanegraphs作者：胡晓雪Author：HUXiaoxue指导教师：王维凡Supervisor：．坠驾整塑墅Major：．OperationalResearchandCybernetics学4i：理学硕士Degree：丛塑圭竺Q!曼里i旦望塑授予单位：堂垄塑垂盘茔Institute：圣塾蜀!呈坠g盟竺!翌坐型垦垫里!曼!垃May,2014万方数据摘要平面图G的一个边一面(或完备)七一染色是指一个映射妒：E(G)UF(G)_{l，2，⋯，七)(v(c)uE(G)ur(a)

2、o{l，2，⋯，岛))，满足对于任意不同的相邻或相关联的元素z，Y∈E(C)uF(G)(z，Y∈v(a)uE(a)uF(G))都有妒扛)≠妒(Ⅳ)．G的边一面(或完备)色数是指G有～个边一面(或完备)七一染色的数k的最小值，用x。，(G)(X。。，(G))表示．若G有一个边一面染色7r，使得对每个z∈E(G)uF(G)都有丌扛)∈工(z)，那么就称G是边一面厶可染的．若对于任意列表IL(z)I≥k，G是边一面L可染的，那么就称G是边一面k一列表可染的．G的边一面列表色数是指G是边一面后一列表可染的数七的最小值，用ches(G)表示．类似的定义完备列表染色，且G的完备列表色数用ch。。

3、，(G)表示．关于平面图的边．面染色问题，最早是由Jucovi琶(1969)和Fiamchik(1971)提出的．后来，Borodin证明了当A(G)≥10时，x。，(G)≤A(G)+1，这个结论．-7pl直接拓展到边一面列表染色．于是，Wang和Lih提出了一个问题：对于任意3≤A(G)墨9的平面图G，确定边一面列表色数ch。，(G)一个紧的上界．平面图的完备染色是Ringel(19651提出的．Borodin在1993年证明了对于任意A(o)≥12的平面图G，)(。。，(G)≤A(G)+2．并且后来他提出了一个问题：对于A(a)≤11的平面图G，能否找到x。。，(G)一个紧的上界

4、?对于平面图的完备列表染色，Borodin证明了对于任意△(G)≥7的平面图G，ch。。，(G)≤△(G)+4．Dong证明了若G是a(a)≥6的平面图，则ch。。，(G)≤A(G)+5．本学位论文主要研究了平面图的边一面染色和完备染色问题，共分四章．第一章我们介绍了基本概念和相关领域的研究现状，并且呈现了本文的主要结果．在第二章中，我们研究了平面图的完备染色，证明了任意A(G)≥9的平面图G是完备(i(a)+2)一可染的．在第三章中，我们研究了平面图的完备列表染色，证明了下面两个结果：(1)任意a(a)≤5的平面图G是完备(zX(G)+5)一列表可染的．(2)任意A(G)≥10的平

5、面图G是完备(A(G)+2)一列表可染的．在第四章我们研究了平面图的边一面列表染色，证明了任意A(G)≥9的平面图G是边一面(A(G)+1)一列表可染的．关键词：边一面列表染色，完备染色，平面图，最大度万方数据AbstractAnedge-face(oranentire)k-coloringofaplanegraphGisamapping妒：E(G)UF(G)叶{1，2，⋯，惫】．(or妒：V(G)UE(G)UF(G)—+{1，2，⋯，尼))，suchthat妒(z)≠妒(可)foreachpairofadjacentorincidentelementsz，Y∈E(G)UF(G)(o

6、rz，Y∈V(G)UE(G)UF(G))．Theedge-facechromaticnumberxes(c)(orentirechromaticnumberx。。，(G))，istheleastnon—negativeintegerksuchthatGhasanedge—face(orentire)k-coloring．IfGhasanedge-facecoloring7r，suchthat丌(z)∈L(z)foreachX∈E(G)UF(G)，thenwesaythatGisedge-faceL-colorable．If,foranylistLsatisfyingIL(z)I≥后f

7、oreachz∈E(C)UF(G)，Gisedge-faceL-colorable，thenGiscallededge-facek-choosable．Thelistedge-facechromaticnumbercheAG)istheleastnon-negativeintegerksuchthatGhasanedge-facek-choosable．Similarly，wecandefinelistentirecoloring，andu8ech。。s(