搜索
AkaddmialKiad6-Springer-VerlagCOMBINATORICA12(2)(1992)125-134COLORINGSANDORIENTATIONSOFGRAPHSN.ALON*andM.TARSIReceivedJuneYH,1989RevisedAugust29,1989Boundsforthechromaticnumberandforsomerelatedparametersofagraphareobtainedbyapplyingalgebraictechniques.Inparticular,thefollowingresultisproved:IfGisadirectedgraphwithmaximumoutdegreed,andifthenumberofEuleriansubgraphsofGwithanevennumberofedgesdiffersfromthenumberofEuleriansubgraphswithanoddnumberofedgesthenforanyassignmentofasetS(v)ofd+1colorsforeachvertexvofGthereisalegalvertex-coloringofGassigningtoeachvertexvacolorfromS(v).1.IntroductionAsubdigraphHofadirectedgraphDiscalledEulerianiftheindegreedH(V)ofeveryvertexvofHinHisequaltoitsoutdegreed+H(v).NotethatwedonotassumethatHisconnected.Hisevenifithasaneven]iumberofedges,otherwise,itisodd.LetEE(D)andEO(D)denotethenumbersofevenandoddEuleriansubgraphsofD,respectively.(ForconvenienceweagreethattheemptysubgraphisanevenEuleriansubgraph.)Ourmainresultisthefollowing:Theorem1.1.LetD=(V,E)beadigraph.ForeachvEV,letS(v)beasetofd+(v)+1distinctintegers,where~D(V)istheoutdegreeofv.IfBE(D)~EO(D)thenthereisalegalvertex-coloringc:V-~Zsuchthatc(v)~S(v)forallvEV.Corollary1.2.LetGbeanundirectedgraph.IfGhasanorientationDsatisfyingEE(D)~EO(D)inwhichthemax/mumoutdegreeisd,thenGis(d+1)-colorable.Inparticular,ifthemaximumoutdegreeisdandDcontainsnoodddirected(simple)cyclethenGis(d+1)-colorable.SinceacompletegraphGond+1verticeshassuchanorientation(i.e.,theacyclicorientation),theupperboundd+1issharp.IncasetheorientationDisacyclic,theconclusionofthetheoremandthatofthecorollarycanbeeasilyprovedbyinduction.ThegeneralcaseseemsInuchmorecomplicatedandouronlyproofforitisalgebraic.Anyupperboundtothechromaticnumberofagraphsuppliesalowerboundtoitsindependencenumber.Theresultingestimatesarestatedinthefollowingtwocorollaries.*ResearchsupportedinpartbyaUnitedStates-IsraelBSFGrantandbyaBergmannMemorialGrant.AMSSubjectClassificationcodes(1991):05C15,05C20126N.ALON,M.TARSICorollary1.3.LetGbeanundirectedgraphonnvertices.IfGhasanorientationDsatisfyingEE(D)#EO(D)inwhichthemax/mumoutdegreeisd,thenGhasanindependentsetofsizeatleastn/(d+1).Inparticular,ifthemax/mumoutdegreeisdandDcontainsnoodddirected(simple)cyclethenGhasanindependentsetofsizeatleastn/(d+1).Notethattheestimaten/(d+1)issharp,asshownbyanyunionofvertex-disjointcompletegraphsond+1verticeseach.AsisthecaseinCorollary1.2theassertionofthelastcorollarycanbeeasilyprovedbyinductioninthespecialcasewhenDisacyclic.However,wedonothaveanon-algebraicproofforthegeneralcase.Corollary1.4.LetGbeanundirectedgraphonasetV={Vl,...,v~}ofnvertices,andsupposeithasanorientationDsatisfyingEE(D)#EO(D).Letdl_d2..._d~nbetheorderedsequenceofoutdegreesofthenverticesofD.Then,foreveryk,nkO,Ghasanindependentsetofsizeatleastr(n-k)/(dk+l+1)1.Theorem1.1actuallydealswiththenotionofchoosabilityofgraphs,introducedandstudiedin[9]and[15].LetG=(V,E)beanundirectedgraphandletf:V--*Z+beafunctionwhichassignstoeachvertexv 9Vapositiveintegerf(v).WesaythatGisf-choosableifforeverychoiceofsetsS(v)ofintegers,whereIS(v)l=/(v)forallvEVthereisalegalcoloringc:V--*Zsuchthatc(v)ES(v)forallvEV.Inparticular,ifGisf-choosablefortheconstantfunctionfgivenbyf(v)=kforeachv 9VwesaythatGisk-choosable.Theorem1.1isclearlyastatementconcerningthechoosabilityofgraphs.Ourpaperisorganizedasfollows:InSection2wepresenttheproofsofTheorem1.1anditsthreeCorollaries.ThisTheoremisappliedinSection3toobtainresultsconcerningthechoosabil.ityofgraphs.ThefinalSection4containssomeconcludingremarksandopenproblems.2.TheProofoftheMainResultOurmethodresemblestheoneweappliedin[3].(Seealso[1]forasimilarapproach.)Westartwiththefollowingsimplelemma.Lemmn2.1.LetP=P(xl,x2,...,xn)beapolynomialinnvariab/esovertheringofintegers7/..Supposethatfor1inthedegreeofPasapolynomialinxiisatmostdiandletSiCZbeasetofdi+1distinctintegers.IfP(xl,x2,...,xn)=0foralln-tuples(Xl,...,xn)ES1x$2x...xSnthenP-O.Proof.Weapplyinductiononn.Forn=1thelemmaissimplytheassertionthatanonzeropolynomialofdegreedlinone-variablecanhaveatmostdldistinctzeros.Assumingthelemmaholdsforn-1weproveitforn,(n2).GivenapolynomialP=P(Xl,...,xn)andsetsSi-satisfyingthehypothesesofthelemma,dnletuswritePasapolynomialinxn,i.e.,P=~Pi(xl,...,xn-1)x~,whereeachi=0Piisapolynomialwithxj-degreeboundedbydj.Foreachfixed(n-1)-tuple(Xl,...,xn-1)6$1x$2x...xSn-1,thepolynomialinxnobtainedfromPbysubstitutingthevaluesofXl,...,xn-1vanishesforallxn 9SnandisthusCOLORINGSANDORIENTATIONSOFGRAPHS127identically0.ThereforePi(xl,...,Xn-1)=0forall(Xl,...,xn-1)ES1x...xSn-1andhence,bytheinductionhypothesis,Pi=-0foralli,implyingthatP_=0.Thiscompletestheinductionandtheproofofthelemma.IThegraphpolynomialfG(Xl,x2,...,Xn)ofanundirectedgraphG=(V,E)onasetV={Vl,...,vn}ofnverticesisdefinedbyfG(Xl,x2,...,Xn)=1]{(xi-xj):ij,{vi,vj}EE}.ThispolynomialisstudiedbyLiandLiin[12],followingapreviousrelatedworkbyGraham,LiandLi([11]).Ananalogouspolynomialforcertainlinearmatroidsisconsideredin[3] 9ItisnottoodifficulttoseethatthecoefficientsofthemonomialsthatappearinthestandardrepresentationoffGasa