浅议平面图染色问题的研究

《浅议平面图染色问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东科技大学硕士学位论文平面图染色问题的研究姓名：方峻峰申请学位级别：硕士专业：计算机应用技术指导教师：吴建良20030501山东科技大学硕士学位论文摘要平面图染色问题的研究方峻峰山东科技大学25003l摘要对平面图G的边面染色，是指对图G的每条边和每个面染上一种颜色，使得相邻的边和面染不同的颜色；边面色数z。(G)是对图G的进行边面染色的最小色数．对平面图G的完备染色，是指对的G每个顶点、每条边和每个面均染上一种颜色，使得相邻的顶点、边和面染不同的颜色；完备色数z。(G)是对圈G的进行完备染色的最小色数．给定平面

2、图G=(y，E)，若存在一个外边g∈E，使得G—P是一个外平面图(即图G—P中所有点都与其无界面相关联)，则称G为几乎外平面图．本文在对外平面图的性质进行深入探讨的基础上，讨论了几乎外平面图的边面染色和完备染色问题．我们证明了对任意几乎外平面图G，其边面色数必满足zF(G)≤ma)({7，△(G)+1}，进而当G是2一连通且△(G)≥6时，有z矿(G)=△；而且其完备色数必满足z。(G)≤ma)【{9，△(G)+2}，进而当G是2-连通且△(G)≥7时，有z．订(G)=△+1．关键词：外平面图，几乎外平面图，边面染

3、色，完备染色山东科技大学硕士学位论文摘要ColoringProblemofPlanarGraphFangJunf醯gshandonguniVers时0fscience柚dTechn010肼Jinan250031AbstractTheedge—facechromaticnumberZ一(G)ofaplanargraphGistheminimalnumberofc010rsneedcdforcoloringmeedgesalldfacesofGsuchthatno押oadjaccntorincidentelements

4、receivethesamec010LTheentirechmmaticnumberz耐(G)ofaplanargr印hGistheminimalnumbcrofc010rsneededforcoloringtheVenices，edgesandfacesofGsuchthatno柳oadjacentorincidcntelementsreceivethcs锄ecoloLLetG=(矿，E)beaplanar日aph，ifmereisaouteredge日∈E，suchmatp—eisaouterplanar铲印h

5、(thatis，a11VerlicesofG—Pareincidem丽mouterface)，tllenGisaIlalmostouterplanar鲫h．h1t11isp印er，basedont11efunllerpropemesofouterplanargr印hs，weinvestigatetheproblemsofmeedge—facec010—ngaIldentirecoloringonalmostouterplanar盯aphs．WeshowthatforanyalmostpIanargraphG，mee

6、dge—facechromalicnumberofGmustsafisfyz盯(G)≤max{7，△(G)+1}，moreover，z盯(G)=△(G)whenGis2一cormectedand△(G)≥6；theentirechromaticnumbermustsatisfyzw(G)≤max{9，△(G)+2)，andz呵(G)=△(G)+1wh朋Gis2．connectedand△(G)≥7．Kely、Nord：oHte，ptnn8rgrl2ph，Ⅱtmostouterpldnnrgrclph，edgeoac

7、echromnticnumb￡rent自．echromnticn“mber声明本人呈交给山东科技大学的这篇硕士学位论文，除所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文尚没有呈交于其它任何学术机构。研究生签名：——日期：——AFFIRMATl0NIdeclarethatthisdissertation，submittedinfuIfillnlentofmcrequirementsfortheawardofMasterofPhilosophy’inShandongUniversityofSc

8、ienceandTecllllology，iswhollymyownworkunlessre凫rencedofacknowledge．Thedocumenthasnotbeensubmittedforqual埔cationataIlyotheracademicinstitute．Signature：——Date=——山东科技定学硕士学位论文引言第一章引言图的