若干圖類的全染色、完備染色和選色問題研究.pdf

1、學(xué)位論文若干圖類的全染色、完備染色和選色問題研究溫宇鵬指導(dǎo)教師王德強(qiáng)教授申請學(xué)位級別理學(xué)碩士專業(yè)名稱應(yīng)用數(shù)學(xué)學(xué)位授予單位大連海事大學(xué)2007年3月英文摘要Onthetotalcoloring，entirecoloringandchoosabilitycoloringofsomegraphsAbstractGraphcoloringisoneofthekeyquestionsingraphtheoryItcomesfromthestudy

2、ofthecelebratedfourcolorproblemIt’sprofoundsignificanceinboththeoryandpracticeNowadays，asthecoloringproblemwaswidelyusediginourrivingithasgraduallybecomeoneofthemostimportantareasofresearchscholarsGraphtheoryisaveryactiv

3、eresearchtopic，variousissueswereraisedandhavebeendevelopeddevelopedapplicationInthispaperwestudiedthetotalcoloringandcompletecoloringoftheregularplanarmeshessquaremesh，hexagonalmeshandhoneycombmeshandthechoosablecoloring

4、oftheplanargraphwithout4cycles，5cyclesandintersectingtrianglesFirst，accordingtothestructuralcharacteristicsofregularplanarmeshes，thetotalcoloringandcompletecoloringofsquaremesh，hexagonalmeshandhoneycombmeshisgiven，aneffe

5、ctivecoloringalgorithmonthetotalcoloringofregularplanarmeshesispresentedWecanfinishthetotalcoloringofregularplanarmeshesinpolynomialtimeThetimecomplexityiso(n2)Weprovedthetotalcllromaticnumberofthethreeregularplanarmeshe

6、sisequaltothemaximumdegreeofthemeshesplus1Thecompletechromaticnumberofsquaremeshandhexagonalmeshisequaltothemaximumdegreeofthemeshesplus3，thechromaticnumberofhoneycombmeshisequaltothemaximumdegreeofthemeshesplus4Thecolor

7、ingmethodsisthebestSecond，weconstructedanewplanargraphwithout4cycles，5cyclesandIntersectingtrianglesIn2006，Montassierconstructedaplanargraphwithout4cyclesand5一cyclesandintersectingtrianglesthatisnot3一choosable(Bordeaux3c