图的点荫度和点线性荫度

图的点荫度和点线性荫度第1页，课件共20页，创作于2023年2月Thevertexarboricityva(G)ofagraphGistheminimumnumberofcolorsthatcanbeusedtocolortheverticesofGsothateachcolorclassinducesaforestofG.Thevertexlineararboricityvla(G)ofagraphGistheminimumnumberofcolorsthatcanbeusedtocolortheverticesofGsothateachcolorclassinduceslinearforestofG.ForanygraphG,第2页，课件共20页，创作于2023年2月Theorem(KronkandMitchem,1975)LetGbeasimpleconnectedgraph.IfGneitheracyclenoracliqueofoddorder,then

第3页，课件共20页，创作于2023年2月Theorem(Matsumoto,1990)LetGbeaconnectedgraph.Then(1)ThereexistsacoloringofGsuchthateachinducedsubgraphhasonlyorasitsconnectedcomponents.(2).(3)Ifforsomepositiveintegern,thenifandonlyifGisacycleor.第4页，课件共20页，创作于2023年2月

Theorem(Akiyama,Era,GervacioandWtanabe,1989)IfGisagraphwithmaximumdegreed,then

第5页，课件共20页，创作于2023年2月

Theorem(CatlinandLai,1995)LetkbeanaturalnumberandletGbeaconnectedsimplegraphwiththatisnotacompletegraph(if)noracycle(ifk=1).Thenandthereisak-coloringofGsuchthateachcolorclassinducesaforest,andsuchthatonecolorclassisamaximuminducedforestinG.第6页，课件共20页，创作于2023年2月

Theorem(CatlinandLai,1995)LetGbeaconnectedsimplegraph,andletkbeapositiveinteger,thenGhasa(k+1)-coloring,whereeachcolorclassisaforest.Furthermore,ifGisnotacompletegraphthenforeachpropertybelow,thiscoloringcanbechosentosatisfythatproperty:(a)onecolorclassisedgelessandonecolorclassmaybeassumedtobeamaximuminducedforest,or(b)onecolorclassmaybeassumedtobeamaximumindependentset.第7页，课件共20页，创作于2023年2月

Theorem(Burr,1986)ForeverygraphG,.Moreover,forevery,thereisaGwithva(G)=a(G)=k.第8页，课件共20页，创作于2023年2月

Theorem(Michem1970)LetGbeanygraphoforderp.Then

Andtheboundsaresharp.第9页，课件共20页，创作于2023年2月

Theorem(Alavi,Green,Liu,Wang,1991)LetGbeanygraphoforderp.Then

andthelowerboundsaresharpexceptforthesuminthecase.第10页，课件共20页，创作于2023年2月

Theorem(Alavi,Liu,Wang,1994)LetGbeanygraphoforderp.Then

andforanygraphGoforder,where,,

andalltheboundsaresharp.第11页，课件共20页，创作于2023年2月

Theorem(Lam,Shiu,Sun,Wang,Yan,2001)IfGisagraphofordern,then

andalloftheboudsaresharp.

Theorem(Lam,Shiu,Sun,Wang,Yan,2001)IfGisagraphofordern,then

andalloftheboudsaresharp.第12页，课件共20页，创作于2023年2月

Theorem(Poh,1990)IfGisaplanargraph,then

第13页，课件共20页，创作于2023年2月

Theorem(杨爱民，1998)

(1)

(2)IfGisatree,then第14页，课件共20页，创作于2023年2月

Theorem(左连翠，吴建良，刘家壮，2006)(1)Ifand,thenforanintervalDbetween1and.

(2)Let,then

forforforfor

第15页，课件共20页，创作于2023年2月

Theorem（马刚，吴建良，2006）(1)IfTisatreewithmaximumdegree，then(2)IfTisatreewithmaximumdegree，then(3)IfGisanouterplanargraphwithmaximumdegree，then第16页，课件共20页，创作于2023年2月

J.Akiyama,H.Era,S.V.Gervacio,andM.Vatanabe,Pathchromaticnumbersofgraphs.J.GraphTheory,13(1989)569-575.Y.Alavi,D.Green,J.Q.LiuandJ.F.Wang,Onlinearvetex-arboricityofgraphs.CongressusNumeratim,1991,82,187-192Y.Alavi,P.C.B.Lam,D.R.Lick,P.Erdos,J.Q.LiuandJ.F.Wang,UpperBoundsonlinear-vertexarboricityofcomplementaryGraphs.UtilitasMath.52,(1997)43-48.Y.Alavi,J.Q.LiuandJ.F.Wang,Onlinearvertex-arboricityofcomplementarygraphs.J.GraphTheory18(1994)315-322.Y.Alavi,D.R.Lick,J.Q.LiuandJ.F.Wang,Boundsforlinearvertex-arboricityanddominationnumberofgraphs.VishnaInternationalJournalofGraphTheory,1992,1(2),95-102.S.A.Burr,Aninequalityinvolvingthevertexarboricityandedgearboricityofagraph.J.GraphTheory10(1986)403-404.P.A.CatlinandH.J.Lai,Vertexarboricityandmaximumdegree.Dis.Math.141(1995)37-46.G.Chartrand,D.P.Geller,andS.Hedetniemi,Ageneralizationofthechromaticnumber.Proc.Camb.Phil.Soc.64(1968)265-271.第17页，课件共20页，创作于2023年2月G.ChartrandandH.V.Kronk,Thepoint-arboricityofplanargraphs.J.LondonMath.Soc.44(1969),612-616.G.Chartrand,H.V.KronkandC.E.Wall,Thepoint-arboricityofagraph.IsraelJ.Math.6(1968).169-175.F.Harary,R.MaddoxandW.Staton.Onthepointlineararboricityofagraph.Mathematiche(Catania)44(1989)281-286.H.V.KronkandJ.Mitchem,Criticalpoint-arboriticgraphs.J.LondonMath.Sco.(2),9(1975),459-466.P.C.B.Lam,W.C.Shiu,F.Sun,J.F.WangandG.Y.Yan,Linearvertexarboricity,independencenumberandcliquecovernumber.ArsCombin.58(2001)121-128.M.Matsumoto,Boundsforthevertexlineararboricity.J.GraphTheory14(1990)117-126.J.Mitchem,Doctoralthesis,WesternMichiganUniversity(1970).K.S.Poh,Onthelinearvertex-arboricityofaplanargraph.J.GraphTheory,14(1990)73-75.J.F.Wang,Onpoint-lineararboricityofplanargraphs.DiscreteMath.72(1988)381-384.第18页，