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

1、學位論文若干圖類的全染色、完備染色和選色問題研究溫宇鵬指導教師王德強教授申請學位級別理學碩士專業(yè)名稱應用數(shù)學學位授予單位大連海事大學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