平面圖的邊染色.pdf

1、1023341學(xué)筏代碼19≥!i研究類型一墨礎(chǔ)雯i蟹一辮江師范史學(xué)碩士學(xué)位論文題目：一一二蔓魚(yú)匣魚(yú)墊釜魚(yú)一一一——學(xué)科專業(yè)：——一一重釜莖墨蕉劍逢——牟級(jí)：2004級(jí)學(xué)號(hào)：2QQ壘2Q!：，3一研究生：一生衛(wèi)壑尚指導(dǎo)教師：量廛煎中圓分類虧：Q!丑L答辯時(shí)間：20嘶一年』王J弓監(jiān)日ABSTRACTEDGECoLoRINGoFPLANARGRAPHSABSTRACTLetG=(VE)beafinite，simpleandundirected

2、graphwiththesetofverticesVandthesetofedgesE，andC=1，2，，忌)，asetofkcolorsAproperkedgecoloringofGisamappingfromEintoCsuchthatnoadjacentedgesreceivethesamecolorIfGhasaproperkedgecoloringthenGissaidtobekedgecolorableThechromat

3、icindexdenotedbyx7(G)，istheleastnonnegativeinteger后suchthatGis南一edge—eolorableAnedgelistassignmentLofGisasetoflistsofcolorswhichassigneachedgeeofGalistofcolorsL(e)IfGhasaproperedgecoloring妒suchthat妒(e)∈L(e)foreverye∈E，th

4、enGissaidtobeL—eolorableIfGisLcolorableforeveYyedge—fistassignmentLwithJ己(e)l—kforeverye∈E，thenwesaythatGisk—listedgecolorable，orkedgechoosableTheedgechoicenumberorlistchromaticindexofG，denotedbyx；(G)，istheleastnon—negat

5、iveintegerksuchthatGiskedgechoosableOnedgecoloringofgraphs，Vizingmadeagreatbreakthroughin1964Heprovedthat∥(G)=△(G)orx7(G)=△1Thisfamoustheoremdividesfinitesimplegraphsintotwoclassesaccordingtotheirchromaticindices，namelMa

6、graphissaidtobeofclasslifx7(G)=△(G)；ofclass2，otherwiseFollowingprecedentworks，thisdissertationstudiesclassificationproblemsofplanargraphsThemainresultsobtainedinthisdissertationsmaybesummarizedasfollows：(1)IfGisaplanargr