30719.平面圖的邊—面染色和完備染色

1、平面圖的邊一面染色和完備染色Edgefacecoloringandentirecoloringofplanegraphs作者：胡曉雪Author：HUXiaoxue指導(dǎo)教師：王維凡Supervisor：墜駕整塑墅Major：OperationalResearchandCybernetics學(xué)4i：理學(xué)碩士Degree：叢塑圭竺Q!曼里i旦望塑授予單位：堂壟塑垂盤塋Institute：圣塾蜀!呈墜g盟竺!翌坐型墾墊里!曼!垃May2014

2、AbstractAnedgeface(oranentire)kcoloringofaplanegraphGisamapping妒：E(G)UF(G)葉1，2，，憊】(or妒：V(G)UE(G)UF(G)—1，2，，尼))，suchthat妒(z)≠妒(可)foreachpairofadjacentorincidentelementsz，Y∈E(G)UF(G)(orz，Y∈V(G)UE(G)UF(G))Theedgefacechromat

3、icnumberxes(c)(orentirechromaticnumberx。。，(G))，istheleastnon—negativeintegerksuchthatGhasanedge—face(orentire)kcoloringIfGhasanedgefacecoloring7r，suchthat丌(z)∈L(z)foreachX∈E(G)UF(G)，thenwesaythatGisedgefaceLcolorableIffo

4、ranylistLsatisfyingIL(z)I≥后foreachz∈E(C)UF(G)，GisedgefaceLcolorable，thenGiscallededgefacekchoosableThelistedgefacechromaticnumbercheAG)istheleastnonnegativeintegerksuchthatGhasanedgefacekchoosableSimilarly，wecandefinelis

5、tentirecoloring，andu8ech。。s(a)todenotelistentirechromaticnumberTheedgefacecoloringofplanegraphsWasfirstconsideredbyJucovi爸(1969)andFiamchik(1971)Borodinprovedthatifa(C)≥10，thenXs(G)≤a(c)1，whichcanbeextendedtothelistedgef

6、acecoloringversionWangandLihaskedforasharpupperboundforch。，(G)whenGisaplanegraphwith3曼a(c)≤9TheentirecoloringofaplanegraphWasintroducedbyRingel(1965)In1993，BorodinprovedthatifGisaplanegraphwith△(G)≥12，thenx。。，(G)≤a(a)2Al

7、soheproposedaquestion：whatisthetightupperboundaboutx”es(a)forplanegraphsGwithZX(G)≤117Moreover，BorodinconfirmedthatifGisaplanegraphwith△(G)27，thench。。，(G)≤a(a)4DongWeiprovedthatifGisaplanegraphwith△(G)≥6，thenclk。s(G)≤a(C

8、)5Inthismasterthesis，westudytheedgefacelistcoloringandentirecoloringofplanegraphsThethesisconsistsoffourchaptersInChapter1，wecollectsomebasicnotations，giveachiefsurveyinthisdirectionandstatethemainresultsobtainedInChapte