construction
HosseinHajiabolhassan1,2
and
XudingZhu1,∗
1
DepartmentofAppliedMathematicsNationalSunYat-senUniversityKaohsiung80424,Taiwan2
InstituteforStudiesinTheoreticalPhysicsandMathematics(IPM)P.O.Box19395–5746,Tehran,Iran
Jan,2001
Abstract
ThispapergivesasufficientconditionforagraphGtohaveitscircularchromaticnumberequalitschromaticnumber.Byusingthisresult,weprovethatforanyintegert≥1,thereexistsanintegernsuchthatforallk≥nχc(Mt(Kk))=χ(Mt(Kk)).
Keywords:Circularchromaticnumber,Mycielski’sgraphs,chromaticnumber.
1Introduction
Allgraphsconsideredinthispaperarefiniteandsimple.SupposeG=(V,E)isagraphandk≥2darepositiveintegers.A(k,d)-colouringofGisamapping
∗
SupportedinpartbytheNationalScienceCouncilundergrantNSC91-2115-M-110-003.
1
c:V→{0,1,···,k−1}suchthatforanyedgexyofG,d≤|c(x)−c(y)|≤k−d.Thecircularchromaticnumberχc(G)ofGisdefinedby
χc(G)=inf{k/d:thereexistsa(k,d)-colouringofG}.
Thecircularchromaticnumber(alsoknownasthestarchromaticnumber)isanaturalgeneralizationofthechromaticnumber(notethata(k,1)-colouringissimplyak-colouring),andhasbeenstudiedextensivelyinthepastdecade,[1,2,4,6,11,12,13,14,15,16].Itisknown[12]thatχ(G)−1<χc(G)≤χ(G)foranygraphG,andtherearegraphsGwithχc(G)=χ(G)aswellasgraphswithχc(G)arbitrarilyclosetoχ(G)−1.ThequestionofwhichgraphsGhaveχc(G)=χ(G)hasattractedsomeattention[1,4,6,11,12,13,14,15].ItisNP-hardtodetermineifagivengraphGhasχc(G)=χ(G)[6].However,somesufficientconditionsforgraphstohaveχc(G)=χ(G)canbefoundintheliterature[1,4,6,11,15,13].
Thispapergivesanothersufficientconditionforgraphstohaveχc(G)=χ(G).ThisconditionisthenappliedtothestudyofthecircularchromaticnumberofMy-cielski’sgraphs,especially,thecircularchromaticnumberoftheiteratedMycielskianofcompletegraphs.
ForagraphGwithvertexsetV(G)=VandedgesetE(G)=E,theMyciel-skianM(G)ofGisthegraphwithvertexsetV∪V∪{u},whereV={x:x∈V},andedgesetE∪{xy:xy∈E}∪{xu:x∈V}.Thevertexxiscalledthetwinofthevertexx(andxisalsocalledthetwinofx);andthevertexuiscalledtherootofM(G).IfthereisnoambiguityweshallalwaysuseuastherootofM(G).Fort≥2,letMt(G)=M(Mt−1(G)).
Thereisaverysimpleformulaforχ(M(G))intermsofχ(G),i.e.,χ(M(G))=χ(G)+1[10],aswellasaverysimpleformulaforχf(M(G))intermsofχf(G),i.e.,χf(M(G))=χf(G)+1/χf(G)[8].(χf(G)denotesthefractionalchromaticnumberofG).However,thereisnosimpleformulaforχc(M(G))intermsofχc(G).
TheproblemofcalculatingthecircularchromaticnumberofMycielski’sgraphshasbeeninvestigatedin[4,3,7].ItturnsoutthatthecircularchromaticnumberofM(G)isnotdeterminedbythecircularchromaticnumberofGalone.Rather,itdependsonthestructureofG.EvenforgraphsGwithverysimplestructure,itisstilldifficulttodetermineχc(M(G)).
2
TheproblemofdeterminingthecircularchromaticnumberoftheiteratedMy-cielskianofcompletegraphswasdiscussedin[3].Itwasconjecturedin[3]thatifn≥t+2≥3,thenχc(Mt(Kn))=χ(Mt(Kn))=n+t.Withcomplicatedarguments,thespecialcasest=1,2ofthisconjecturehavebeenprovedin[3,4].Asimplerproofofthesespecialcaseswasgivenin[4](fort=2,theresultprovedin[4]isslightlyweaker,i.e.,itwasprovedin[4]thatforn≥5,χc(M2(Kn))=χ(M2(Kn))=n+2).Weshallproveinthispaperthatforanyintegert≥1,ifn≥2t+2thenχc(Mt(Kn))=χ(Mt(Kn))=n+t.
2
Asufficientconditionforχc(G)=χ(G)
Fork≥2dandgcd(k,d)=1,letGkdbethegraphwithvertexset{0,1,···,k−1}andinwhichj∼jifandonlyifd≤|j−j|≤k−d.AhomomorphismfromagraphG=(V,E)toagraphG=(V,E)isamappingf:V→Vsuchthatf(x)f(y)∈Ewheneverxy∈E.Itiswellknown[16]andeasytoseethatifGadmitsahomomorphismtoGthenχc(G)≤χc(G).Itfollowsfromthedefinitionthata(k,d)-colouringofagraphGissimplyahomomorphismfromGtoGkd.Whenconsideringa(k,d)-colouringofG(orequivalently,ahomomorphismfromGtoGkd),weviewthecolours0,1,···,k−1ascyclicallyordered.Fora,b∈{0,1,···,k−1},theinterval[a,b]kmeanstheintervalfromatobinthiscyclicorder.Forexample,[2,5]k={2,3,4,5}and[5,2]k={5,6,···,k−1,0,1,2}.Thefollowinglemmaisaneasyconsequenceofaresultof[13].
Lemma1SupposeG=(V,E)isagraphwithχc(G)=k/dandthatc:V→{0,1,···,k−1}isa(k,d)-colouringofG.Thenforeachi∈{0,1,···,k−1},thereexistsavertexxwithc(x)=iwhichisadjacenttoavertexywithc(y)=i+d.Heretheadditionismodulok.
Proof.Assumetothecontrarythatthereexistsanindexisuchthatnovertexofcolouriisadjacenttoavertexofcolouri+d.Lete=i(i+d).ThenthecolouringcisahomomorphismfromGtoGkd−e.However,itwasprovedin[13]
k
thatχc(Gkd−e) SupposeG=(V,E)isagraph.ForavertexxofG,wedenotebyNG(x)thesetofnon-neighboursofx,i.e.,NG(x)={y:y∼x, y=x}.ForX⊆V,let NG(X)=∪x∈XNG(x).Withanabuseofnotation,foranysubsetXofV,weshallalsouseXtodenotethesubgraphofGinducedbyX.WesayY⊆NG(X)isapointwise-dominatingsetofNG(X)ifforeachx∈X,NG(x)−Yisanindependentset.WedefineaparameterβG(X)asfollows: βG(X)=min{|Y|:Yisapointwise-dominatingsetofNG(X)}. Theorem2SupposeG=(V,E)isagraphandXisacliqueofG.Ifχc(G)=k/d(withgcd(k,d)=1),then |X|(d−1)≤2βG(X). Proof.Letc:V→{0,1,···,k−1}bea(k,d)-colouringofG.Itiswellknown[2,12](andalsofollowsfromLemma1)thatcmustuseeverycolour.AssumethatX={x1,x2,···,xm}andc(xi) LetYbeapointwise-dominatingsetofNG(X)with|Y|=βG(X). ConstructabipartitegraphHwithX,Yasitstwopartssothatxi∼yifandonlyif c(y)∈[c(xi)−d+1,c(xi)+d−1]k−{c(xi)}. WeshallshowthateachvertexofXhasdegreeatleastd−1inHandeachvertexofYhasdegreeatmost2inH. Supposexi∈Xandc(xi)=a.Foreach∈{1,2,···,d−1},Aa−d+∪Aa+⊆NG(xi).ByLemma1,thereexistsanedgejoiningavertexofAa−d+toavertexofAa+.SinceNG(xi)−Yisanindependentset,weconcludethatAa−d+∪Aa+containsatleastonevertexofY.Itfollowsthatxihasdegreeatleastd−1inH. 4 Supposey∈Yandc(y)∈[c(xi),c(xi+1)]k.SinceXisaclique,weknowthatforanyxj∈Xwherej=i,i+1, [c(xj)−d+1,c(xj)+d−1]k∩[c(xi),c(xi+1)]k=Ø. Thereforey∼xjinH.Soyhasdegreeatmost2inH.Hence |X|(d−1)≤|E(H)|≤2|Y|, andtheproofiscomplete. Corollary3IfGhasacliqueXsuchthat|X|>2βG(X),thenχc(G)=χ(G).Proof.Otherwiseχc(G)=k/dforsomek,dwithgcd(k,d)=1andd≥2.ByTheorem2,wehave|X|≤|X|(d−1)≤2βG(X),contrarytoourassumption. Corollary3canbegeneralizedtothefollowing: Theorem4SupposeG=(V,E)isagraph.IfthereexistsasubsetX⊆Vsuchthatχ(X)>2βG(X),thenχc(G)=χ(G). Proof.Assumetothecontrarythatχc(G)=k/dforsomed≥2(and(k,d)=1).Letcbea(k,d)-colouringofG.Wechooseasequence{x1,x2,···,xs}asfollows:Letx1∈Xbeavertexforwhichc(x1)=min{c(x):x∈X}.Supposexi∈Xhasbeenchosen.Ifthereisavertexx∈Xwithc(x)≥c(xi)+d,thenletxi+1∈Xbeavertexforwhichc(xi+1)=min{c(x):x∈X,c(x)≥c(xi)+d}.Otherwise,leti=sandtheconstructionofthesequenceiscompleted.Letf:X→{1,2,···,s}bedefinedasf(x)=iifc(xi)≤c(x) playingtherolesoftheverticesoftheclique.Incased=2,theargumentisexactlythesame.Incased≥3,weneedtobecareful,becauseinthebipartitegraphHconstructedintheproofofTheorem2,thoseverticesofYwhosecolourslieintheinterval[c(xs−1),c(xs)]kand[c(x1,c(x2)]kmayhavedegreegreaterthan2.Sowedonothaveχ(X)(d−1)≤2βG(X),butitiseasytoshowthatχ(X)≤2βG(X),contrarytoourassumption.Theargumentissimilar,andweomitthedetails. 5 3Mycielski’sgraphs SupposeG=(V,E)isagraphandM(G)=(V∪V∪{u},E)istheMycielskianofG.IfXisasubsetofV,thenwealsoconsiderXasasubsetofV(M(G))(becauseVisasubsetofV(M(G))).Recallthatforx∈V,thetwinofxisdenotedbyx.ForasubsetXofV,weshalldenotebyXthesetoftwinsofverticesinX,i.e.,X={x:x∈X}. Lemma5LetM(G)betheMycielskianofG.ThenforanysubsetXofV(G),βM(G)(X)≤2βG(X)+1. Proof.Itiseasytoseethatforanyvertexx,ifS=NG(x),thenNM(G)(x)=S∪S∪{x,u}.LetZ=NG(X).Then NM(G)(X)=Z∪Z∪X∪{u}. LetYbeapointwise-dominatingsetofNG(X)with|Y|=β(X).TocompletetheproofofLemma5,itsufficestoshowthatY∪Y∪{u}isapointwise-dominatingsetofNM(G)(X). Letx∈Xanda,b∈NM(G)(x)−(Y∪Y∪{u}).Weneedtoprovethata∼b.NotethatNM(G)(x)⊆Z∪Z∪{x,u}.Assumetothecontrarythata∼b.SinceZ∪{x}isanindependentset,wehave{a,b}⊆Z∪{x}.SinceYisapointwise-dominatingsetofNG(X),itfollowsthat{a,b}⊆Z.Thuswemayassumethata∈Z−Yandb∈(Z∪{x})−Y.ButxisnotadjacenttoanyvertexofNG(x).Thereforeb=x.Assumethatb=c.Thenc∈Z−Y.Nowa∼cimpliesthata∼c,contrarytotheassumptionthatYapointwise-dominatingsetofNG(X).Corollary6SupposeGisagraphandXisasubsetofV(G).Thenfort≥1, βMt(G)(X)≤2tβG(X)+2t−1. Proof.ByLemma5,βMt(G)(X)≤2(βMt−1(G)(X))+1.Theconclusionfollowsbyinduction. 6 Corollary7SupposeGisagraph,t≥1andχc(Mt(G))=k/d(wheregcd(k,d)=1).IfXisacliqueofGthen |X|(d−1)≤2t+1βG(X)+2t+1−2. Corollary8IfGhasacliqueXsuchthat|X|≥2t+1βG(X)+2t+1−1,thenχc(Mt(G))=χ(Mt(G)). InCorollary8,thecliqueXcanbereplacedbyanysubgraphXofG,with|X|bereplacedbyχ(X)(seeTheorem4). Corollary9LetGbeagraphonnverticesandXthesetofverticesofdegreen−1.If|X|≥2t+1−1,thenχc(Mt(G))=χ(Mt(G)). Proof.SinceeachvertexofXhasdegreen−1,itfollowsthatNG(X)=Ø.SoXisacliquewithβG(X)=0.TheconclusionfollowsfromCorollary8. Thespecialcaset=1ofCorollary9wasprovedin[4].Corollary10Ifn≥2t+1−1,thenχc(Mt(Kn))=χ(Mt(Kn)). 4Someimprovements ForthecircularchromaticnumberoftheiteratedMycielskianofcompletegraphs,thefollowingwasconjecturedin[3]: Conjecture1[3]Ifn≥t+2,thenχc(Mt(Kn))=χ(Mt(Kn)). Foranyintegert≥1,letn(t)betheminimumintegersuchthatforanyn≥n(t),χc(Mt(Kn))=χ(Mt(Kn)).Corollary10showsthatforanyt≥1,theintegern(t)existsandn(t)≤2t+1−1.Itwasshownin[3]thatn(t)≥t+2.Thereforewehave t+2≤n(t)≤2t+1−1. Conjecture1aboveisequivalenttosayingthatn(t)=t+2. 7 Fort=1,theupperandlowerboundforn(t)coincideandwehaven(1)=3.Fort=2,Conjecture1wasprovedin[3].Hencen(2)=4.Fort≥3,thereisabiggapbetweentheupperandlowerboundsforn(t).Inthissection,weshallslightlyimprovetheupperboundforn(t). InTheorem2,thecardinalityofaminimumpointwise-dominatingsetYofNG(X)isusedtoboundthecardinalityofX.AcarefulanalysisoftheproofofTheorem2showsthatwhatreallymattersisthenumberofcolourclassesofa(k,d)-colouringofGthatcontainelementsofY.Byfindinga(k,d)-colouringthatcolourssomepairsofelementsofYwiththesamecolours,weprovethefollowingresult,whichisastrengtheningofTheorem2. Theorem11SupposeGisagraphandXisacliqueofG.Ifχc(M(G))=k/d(wheregcd(k,d)=1),then (|X|−3)(d−1)≤2βG(X). Proof.LetYbeapointwise-dominatingsetofNG(X)with|Y|=βG(X).BytheproofofLemma5,weknowthatD=Y∪Y∪{u}isapointwise-dominatingsetofNM(G)(X). TheremainderoftheproofissimilartothatofTheorem2.However,insteadofthecardinalityofD,wecountthenumberofcolourclassesthatcontainanelementofDina(k,d)-colouringofM(G). Letfbea(k,d)-colouringofM(G).Weconstructanew(k,d)-colouringfofM(G)asfollows: f(x)=f(x)ifx∈Yorx=v∈Yandf(v)∈[f(u)−d+1,f(u)+d−1]k;f(v)=f(v)ifv∈Yandf(v)∈[f(u)−d+1,f(u)+d−1]k. Itiseasytoverifythatfisstilla(k,d)-colouringofM(G).Bythedefinition,thereareatmostβG(X)colourclasses(f)−1(i)suchthati∈[f(u)−d+1,f(u)+d−1]kand(f)−1(i)containsanelementofD. Let T={i:0≤i≤k−1,(f)−1(i)∩D=Ø}, 8 andlet T=T−[f(u)−d+1,f(u)+d−1]k. Theargumentaboveshowsthat |T|≤βG(X). NowweconstructabipartitegraphHwithvertexX∪Tandinwhichx∈Xisadjacenttoi∈Tifi∈[f(x)−d+1,f(x)+d−1]k. ThesameargumentasintheproofofTheorem2showsthateachvertexofXhasdegreeatleastd−1,andeachvertexinThasdegreeatmost2. SinceXisaclique,thecoloursofelementsofXarefarapartfromeachother(i.e.,f(x)∈[f(y)−d+1,f(y)+d−1]kifx,y∈Xandx=y).Let X={x∈X:NH(x)∩[f(u)−d+1,f(u)+d−1]k=Ø. Easycalculationsshowthat|X|≤4. If|X|≤3,thenwehave (|X|−3)(d−1)≤2βG(X). If|X|=4,thenbycalculatingthedistancebetweenthecoloursofelementsofX,onecanshowthattherearetwoverticesa,b∈Xsuchthat |([f(a)−d+1,f(a)+d−1]k∪[f(b)−d+1,f(b)+d−1]k)∩[f(u)−d+1,f(u)+d−1]k|≤d−2.ThiswouldimplythatthereareatleastdedgesofHjoiningaandbtoverticesofT. Therefore 2βG(X)−d≥(|X|−4)(d−1), whichisequivalentto (|X|−3)(d−1)≤2βG(X)−1. Thiscompletestheproof. 9 Corollary12SupposeGisagraph,t≥1andχc(Mt(G))=k/d(wheregcd(k,d)=1).IfXisacliqueofGthen (|X|−3)(d−1)≤2tβG(X)+2t−2. Proof.NotethatMt(G)=M(Mt−1(G))andXisacliqueofMt−1(G).ByCorollary6,βMt−1(G)(X)≤2t−1βG(X)+2t−1−1.TheresultfollowsfromTheorem11. Fort≥2,thefollowingareimprovementsofCorollaries9and10,respectively.Corollary13LetGbeagraphonnverticesandXthesetofverticesofdegreen−1.If|X|≥2t+2,thenχc(Mt(G))=χ(Mt(G)).Corollary14Ifn≥2t+2,thenχc(Mt(Kn))=χ(Mt(Kn)). Fort=3,Corollary14assertsthatχc(M3(Kn))=χ(M3(Kn))forn≥10.Conjecture1assertsthatχc(M3(Kn))=χ(M3(Kn))forn≥5.BypushingfurtherthetechniqueusedintheproofofTheorem11(withamorecomplicatedargument),onecanshowthatχc(M3(Kn))=χ(M3(Kn))forn≥8.Itremainsunknownifχc(M3(Kn))=χ(M3(Kn))forn=5,6,7. Itwasprovedin[4]aswellasinSection2(Corollary9)thatifann-vertexgraphGhas3verticesofdegreen−1thenχc(M(G))=χ(M(G)).Thefollowingisanimprovementofthis. Theorem15LetG=(V,E)beagraphonn≥3vertices.IfGhas2verticesofdegreen−1,thenχc(M(G))=χ(M(G)). Proof.Leta,bbetwoverticesofGofdegreen−1.Leta,bbethetwinsofa,b,respectivelyinM(G),andletubetherootofM(G).Assumetothecontrarythatχc(M(G))=k/dforsomed≥2(andgcd(k,d)=1).Letfbea(k,d)-colouringofM(G).Assumef(a)=i.Thennoneoff−1(i−d+1),···,f−1(i+d−1)isemptyandeachcontainsonlyverticesthatarenotadjacenttoa.However,theonlyverticesofM(G)notadjacenttoaareaandu.Sowemusthaved=2and,say,f−1(i−1)={a},f−1(i)={a}andf−1(i+1)={u}. 10 Bysymmetry,wehavef−1(i+2)={b}andf−1(i+3)={b}.Sincen≥3,Ghasverticesotherthanaandb.Nowforeachvertexx∈V−{a,b},sincef(x)∈{f(u)−1,f(u),f(u)+1},wecanassumethatf(x)=f(x)(iff(x)=f(x),wecanrecolourxwiththecolourofxtoobtainanother(k,d)-colouringofM(G)).SinceeveryvertexofV−{b}isadjacenttob,andsincef(x)=f(x)foreveryx∈V−{a,b},weconcludethatf−1(i+4)=Ø.ButthisiscontrarytoLemma1.Theorem15issharpinthesensethattherearegraphsGwithoneuniversalvertexforwhichχc(M(G))=χ(M(G)).LetW2n+1betheoddwheelwhichisob-tainedfromtheoddcycleC2n+1byaddingauniversalvertex.Thenforn≥2,itiseasytoshowthatχc(M(W2n+1))≤4.5<χ(M(W2n+1)),andtheargumentasintheproofofTheorem15showsthatχc(M(W2n+1))≥4.5.Henceχc(M(W2n+1))=4.5,whichwasconjecturedin[9]. References [1]H.L.AbbottandB.Zhou,Thestarchromaticnumberofagraph,J.Graph Theory,17(1993),349-360. [2]J.A.BondyandP.Hell,Anoteonthestarchromaticnumber,J.GraphTheory, 14(1990),479-482. [3]G.J.Chang,L.Huang,andX.Zhu,ThecircularchromaticnumberofMycielski’s graphs,DiscreteMathematics,205(1999),23-37. [4]G.Fan,CircularchromaticnumberandMycielskigraphs,manuscript,2000.[5]D.C.Fisher,Fractionalcolouringswithlargedenominators,J.GraphTheory, 20(1995),403-409. [6]D.R.Guichard,Acyclicgraphcolouringandthecomplexityofthestarchromatic number,J.GraphTheory,17(1993),129-134. [7]L.HuangandG.J.Chang,ThecircularchromaticnumberoftheMycielskian ofGdk,J.GraphTheory,32(1999),63-71. [8]M.Larsen,J.Propp,andD.Ullman,ThefractionalchromaticnumberofMy-cielski’sgraphs,J.GraphTheory,19(1995),411-416. 11 [9]K.W.Lih,L.Tong,andW.Wang,Acyclicorientationsandthecircularchro-maticnumberofagraph,manuscript. [10]J.Mycielski,Surlecolouriagedesgraphes,Colloq.Math.,3(1955),161-162.[11]E.SteffenandX.Zhu,Onthestarchromaticnumbersofgraphs,Combinatorica, 16(1996),439-448. [12]A.Vince,Starchromaticnumber,J.GraphTheory,12(1988),551-559.[13]X.Zhu,Starchromaticnumbersandproductsofgraphs,J.GraphTheory, 16(1992),557-569. [14]X.Zhu,UniquelyH-colourablegraphswithlargegirth,J.GraphTheory, 23(1996),33-41. [15]X.Zhu,Graphswhosecircularchromaticnumberequalthechromaticnumber, Combinatorica,19(1999),139-149.[16]X.Zhu,Thecircularchromaticnumber,asurvey,DiscreteMathematics, 229(2001),371-410. 12 因篇幅问题不能全部显示，请点此查看更多更全内容