11373.平面圖的2距離染色

1、平面圖的2一距離染色作者商春慧指導(dǎo)教師卜月華學(xué)位類別里堂亟學(xué)科專業(yè)運(yùn)簽堂皇撞爿詮學(xué)馘予單位浙江婭蕉太蘭論文提交日期2016年3月23日2DistanceColoringofPlanarGraphsABSTRACTCallagraphGplanarifitcanbedrawnintheplanesuchthatanytwoofitsedgesintersectonlyattheirendsAllgraphsinthispaperaresi

2、mple，finiteandplanargraphsThek2distancecoloringofagraphGisamapping妒：V一(1，，后)suchthatI妒(t正)一妒(口)I≥1ifodG(亂，“)≤2The2一distancechromaticnumber)(2(G)istheleastksuchthatGhasak2一distancecoloringThelist2distancechromaticnumberof

3、Gistheleast后suchthatforeverylistLofsizek，Ghasa2distancecoloring妒，妒(u)∈L(v)wheneveru∈y(G)，denomdby)(5(G)Theresearchof2distancecoloringofplanargraphsoriginatedformWegner’Sconjecturewhichposedinhisreportin1977：assumeGisapla

4、nargraph，then(1)x2(G)≤7ifa(c)=3；(2)x2(G)≤A(G)5if4≤A(G)≤7；(3)x2(G)≤l；△(G)J1ifa(C)≥8Wegner’sconjectureisstillopenButsometimesfightupperboundofplanegraphs’2distancechromaticnumbercanbeprovedWangandCaiproposedaproblem：suppos

5、eGisaplanegraphwithout4cycles，findtheleasttsuchthatx2(G)≤a(c)tThispaperfocuseson2distance(1ist)coloringofplanargraphswithoutshortcyclesInthefirstchapmLweintroducesomedefinitionsandgiveabriefsurveyInthesecondchapterwemain

6、lydiscusslist2distancecoloringofplanargraphswithg(c)≥5andg(c)≥6Inthethirdchapterwestudythelist2distancecoloringofplanargraphswithout4，5cyclesInthefourthchapterwestudy2distancecoloringofplanargraphswithout4cyclesKEYWORDS：