圖的BB-染色.pdf

1、圖的船一染色TheBackboneColoringofGraphsAuthor：旦壘QX墜墮Q衛(wèi)g指導(dǎo)老師：b且垡Supervisor：專業(yè)：熬堂Major：BuYhehuaMathematicsMasterofScience授予單位：塹塑婭菹太堂Institute：丕叢必i翌墜g№!磐壘!衛(wèi)望垃￡塑迎May22，2015TheBackboneColoringofGraphsABSTRACTLetVbeasetofn(凡0)elemen

2、tsEbeasetofbysomebinarysubsetofVCallapairG=(VE)isagraph，theelementsofVandEarethevertexandedgeofGThesetVandEarethevertexsetandedgesetofGLetGbeagraphandHbeaspanningsubgraphofGAbackbone—k—coloringof(G，H)isamapping妒：VIa)—l，2

3、，～，琵)suchthat1妒(札)一壚(u)i≥2ifuvEE(H)andI妒(亂)一妒(口)f≥1iftV∈E(G)＼E(日)，Thebackbonechromaticnumberof(G，H)isdenotedbyxb(a，H)=minklGisbackbone—k—colorableAbackbone—L—coloringof(G，胃)isabackbonecoloringCof(G，H)，suchthat∈L(v)foreve

4、ryvertexVWesay(G，H)isbackbone—L—colorableifthereexistsabackbone—L—coloringof(G，日)Furthermore，wesay(G，日)isbackbone—k—choosableif(G，H)isbackbone—L—colorableforanylistassignmentLwithL(∞)l三是forallV∈y(G)Thebackbonechoicenumbe

5、rof(G，日)isdenotedbyChBB(G，日)=min路l(G，日)Iisbackbone一七一choosableOnthebackbonecoloringofplanargraphs，alotofresearchhasbeenmadeInchapter2，weshowthatifGisaconnectedplanargraphand3cyclesisnotadjacenttO5cycles，thenthereexistsas

6、panningtreeTofGsuchthatxb(G，T)≤4Inchapter3，weshowthatifGisGfreeorG—freeorGfreeandwithoutadjacent4cycles，thenthereexistsaspanningtreeTofGsuchthatxb(G，T)S4TheresultsgeneralizethesufficientconditionfortheplanargraphsofBB4co