Citation
Problems in structural and extremal graph theory

Material Information

Title:
Problems in structural and extremal graph theory
Creator:
Diemunsch, Jennifer L. ( author )
Language:
English
Physical Description:
1 electronic file (80 pages). : ;

Subjects

Subjects / Keywords:
Graph theory ( lcsh )
Graph coloring ( lcsh )
Graph labelings ( lcsh )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Review:
The research in this dissertation can be placed into two broad categories: structural and extremal graph theory. Extremal graph theory seeks to determine maximum and minimum values of graph parameters that ensure (or prohibit) particular graph properties. Structural graph theory considers the substructures of a graph, such as paths, cycles, and matchings, and considers conditions that guarantee the existence (or non-existence) of such graph structures. The work in this dissertation considers three distinct problems: rainbow-matching ; 2-factor ; and graph-packing.
General Note:
Thesis (Ph.D.)--University of Colorado Denver.
Bibliography:
Includes bibliographic references.
System Details:
System requirements: Adobe Reader.
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Jennifer L. Diemunsch.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
910882966 ( OCLC )
ocn910882966

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

PROBLEMSINSTRUCTURALANDEXTREMALGRAPHTHEORY by JENNIFERL.DIEMUNSCH B.S.,TheUniversityofDayton,2009 M.S.,TheUniversityofColoradoDenver,2012 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoinpartialfulllment oftherequirementsforthedegreeof DoctorofPhilosophy AppliedMathematics 2015

PAGE 2

ThisthesisfortheDoctorofPhilosophydegreeby JenniferL.Diemunsch hasbeenapprovedforthe DepartmentofMathematicalandStatisticalSciences by MichaelJacobson,Chair MichaelJ.Ferrara,Advisor EllenGethner FlorianPfender PaulS.Wenger April24,2015 ii

PAGE 3

Diemunsch,JenniferL.Ph.D.,AppliedMathematics ProblemsinStructuralandExtremalGraphTheory ThesisdirectedbyAssociateProfessorMichaelJ.Ferrara ABSTRACT Theresearchinthisdissertationcanbeplacedintotwobroadcategories:structuralandextremalgraphtheory.Extremalgraphtheoryseekstodeterminemaximum andminimumvaluesofgraphparametersthatensureorprohibitparticulargraph properties.Forinstance,wemayconsiderthethresholdfortheminimumdegreeofa graph G thatguaranteestheexistenceofahamiltoniancycle,whichisacyclethat spanstheverticesof G .Structuralgraphtheoryconsidersthesubstructuresofa graph,suchaspaths,cycles,andmatchings,andconsidersconditionsthatguarantee theexistenceornon-existenceofsuchgraphstructures.Forexample,wemayuse thefactthatagraph G doesnotcontainanyoddcyclestoforce G tobebipartite. Theworkinthisdissertationconsidersthreedistinctproblems. A rainbowmatching inanedge-coloredgraphisamatchinginwhichalltheedges havedistinctcolors.In2011,Wangaskedifthereisafunction f suchthata properlyedge-coloredgraph G withminimumdegree andorderatleast f must havearainbowmatchingofsize .Weanswerthisquestioninthearmative;an extremalapproachyieldsthat f =98 = 23 < 4 : 27 suces.Furthermore,we givean O G j V G j 2 -timealgorithmthatgeneratessuchamatchinginaproperly edge-coloredgraphoforderatleast6 : 5 A2 -factor inagraphisaspanning2-regularsubgraph,orequivalentlyaspanning collectionofdisjointcycles.Weinvestigatetheexistenceof2-factorswithabounded numberofoddcyclesinagraph.WeextendresultsofRyjacek,Saito,andSchelp [Closure,2-factors,andcyclecoveringsinclaw-freegraphs, J.GraphTheory 32 iii

PAGE 4

,no.2,109-117]andshowthatthenumberofoddcomponentsofa2-factorin aclaw-freegraphisstableunderRyjacek'sclosureoperation.Additionallya2-factor withnooddcyclesisequivalenttoapairofdisjointperfectmatchings,andweconsider conditionsforthisspeciccase.Mostsignicantly,weshowthata f K 1 ; 4 ;P 4 g -free graphofevenordercontainsdisjointperfectmatchingsorisamemberofaparticular familyofgraphs. Asequence = d 1 ;:::;d n is graphic ifthereisasimplegraph G withvertexset f v 1 ;:::;v n g suchthatthedegreeof v i is d i .Wesaythatgraphicsequences 1 = d 1 ;:::;d n and 2 = d 1 ;:::;d n pack ifthereexistedge-disjoint n -vertex graphs G 1 and G 2 suchthatfor j 2f 1 ; 2 g d G j v i = d j i forall i 2f 1 ;:::;n g Weproveseveralextremaldegreesequencepackingtheoremsthatparallelcentral resultsandopenproblemsfromthegraphpackingliterature.Specically,themain resultofthischapterimpliesadegreesequencepackinganaloguetotheBollobasEldridge-Catlingraphpackingconjecture[Packingsofgraphsandapplicationsto computationalcomplexity, J.Combin.TheorySer.B 25 ,105{124;Embeddingsubgraphsandcoloringgraphsunderextremaldegreeconditions, Ph.D.Thesis OhioStateUniversity,1976]alongwithadegreesequenceversionoftheSauer-Spencer Theorem[Edgedisjointplacementofgraphs, J.Combin.TheorySer.B 25 295{302]. Theseresultsarerelatedinparttodiscretetomography,abranchofdiscreteimagingscience,inwhichthegoalistoreconstructdiscreteobjectsusingdataacquired fromlow-dimensionalprojections.Specically,inthe k -colordiscretetomography problem thegoalistocolortheentriesofan m n matrixusing k colorssothateach rowandcolumnreceiveaprescribednumberofentriesofeachcolor.Thisproblemis equivalenttopackingthedegreesequencesof k bipartitegraphswithpartsofsizes m and n .HerewemodifyourtechniquestoproveseveralSauer-Spencer-typetheorems thathavedirectapplicationstothe2-colordiscretetomographyproblem. iv

PAGE 5

Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:MichaelJ.Ferrara v

PAGE 6

DEDICATION Tomyfamily,fortheirunendingsupport,condence,andprayers. vi

PAGE 7

ACKNOWLEDGMENT TherearesomanypeoplewhoImustthankfortheirsupportthroughoutmy timeasagraduatestudent.Firstandforemost,myadvisor,MikeFerrara,whohas alwayssaidthatnomatterwhatatleastoneofheorIwouldbelieveIcouldcomplete myPhD.Thishasbeentrue,andmoreoftenthannot,hehashadtopulltheweight onbelievingIcouldcompletethis.Ialsoamindebtedtotheothermembersofmy committee:MikeJacobson,PaulWenger,FloPfender,andEllenGethner.Their helphascomeinsupportofmyresearch,outreachopportunities,andremindersto enjoygraduateschool. IowethankstotheNSFGrant#074324UCDGK-12TransformingExperiencesLearningCommunitiesProject"andtheLynnBatemanMemorialFellowship forfundingpartsofthisresearch. Therearecountlessotherswhohavehelpedmeonmyway.Firstly,ArtBusch, whointroducedmetographtheory;SogolJahanbekamwhomaderesearchfarmore funevenifmoredisorganized;andmyotherco-authorssuchasJamesShook.My fellowgraduatestudentshavegreatlyhelpedovertheyearsandIcannotthankthem enough:HencBouwmeester,JeLarsen,EricSullivan,andBreeannFleschgave meencouragement,wisdom,andfriendship;thebeginningofthisjourneybeganwith studyingforcoursesandprelimswithMarkMueller,CathyErbes,PhilDeOrsey,Brad Lowery,andTimMorris;AxelBrandt,DanielYorgov,DevonSigler,ReidMessersmith,StephaniePatterson,ScottWalsh,TugulukeAbulitibu,BrentThomasand TKMillerhaveprovidedrideshome,listeningears,andhappyhourcompanionsover theyears;nally,thankyoutoNathanGraber,LukeNelsen,andEricSullivan formakingmynalyearsuchfun.WordscannotexpressmygratitudetoGaryOlson andNoraJennings,twoofmybestfriends{theirsupportthroughprayers,movie nights,dinnersout,etc.areunmatched.Myentirefamilyhasbeenwithmeinthis journey,whichhasbeeninvaluable.Inparticular,mybrotherhasalwayssupported mydecisions;mysister,brother-in-law,andnephews,whofoundtimetovisitoften andmotivatedmetonevergiveup;andmyparents,whohavegivenmeencouragementineverypossibleway.Lastly,anyonewhohasenjoyeddessertovertheyears, thankyou. vii

PAGE 8

TABLEOFCONTENTS Figures.......................................x Chapter 1.Introduction...................................1 1.1DenitionsandNotation........................1 1.2OverviewofStructuralandExtremalGraphTheory.........3 2.RainbowMatchingsinProperlyEdge-ColoredGraphs............7 2.1Introduction...............................7 2.2ProofofTheorem2.1..........................9 2.3ProofofTheorem2.2..........................17 3.2-FactorswithaBoundedNumberofOddComponents...........23 3.1Introduction...............................23 3.2Closureand odd G forClaw-FreeGraphs...............25 3.3Disjoint1-factors.............................34 3.3.1ForbiddenSubgraphConditions.................35 3.3.2MinimumDegreeandConnectivityConditions........39 4.ExtremalTheoremsforDegreeSequencePacking..............41 4.1Introduction...............................41 4.1.1GraphPacking..........................42 4.1.2PackingGraphicSequences...................43 4.1.3StatementofMainResults....................44 4.2Sharpness.................................45 4.3ProofsofTheorem4.4,Corollary4.5,andCorollary4.6.......47 4.4DiscreteTomography..........................55 4.4.1The k -colorTomographyProblem................56 4.4.2ASauer-Spencer-typeTheoremfortheDiscreteTomography Problem..............................56 viii

PAGE 9

5.FutureWorkandOpenProblems.......................61 5.1RainbowMatchingsinEdge-ColoredGraphs.............61 5.2OpenProblemsandConjecturesRegarding2-factorswithaBounded NumberofComponents.........................62 5.3DegreeSequenceandMixedPackingProblems............63 References ......................................65 ix

PAGE 10

FIGURES Figure 3.1Thefamily E of2-connected f K 1 ; 4 ;P 4 g -freegraphsthatdonotcontain disjoint1-factors................................36 3.2Thegraph P 4 ..................................40 x

PAGE 11

1.Introduction 1.1DenitionsandNotation A graph G isanorderedpairofdisjointsets V;E ,suchthat E isasubsetof V V ,ofunorderedpairsofverticesin V .Wecall V the vertexset and E the edge set .Agraph G has order j V j and size j E j .Fortwovertices, u and v in V ,if u;v isin E u and v are adjacent ,andforsimiplicityweoftenwrite uv 2 E .Thenumber ofedgesincidenttoavertex v isthe degree of v ,denoted d G v .Thesetofvertices adjacentin G to v isthe neighborhood of v ,denoted N G V .Thus,wehavethat j N G v j = d G v .Wedenotetheminimumdegreeoverallverticesin G as G ,and likewisethemaximumdegreeoverallverticesin G as G .Wheneveryvertexof G hasdegree r ,whichistosaythat G = G = r G is r -regular .Wewilloften dropthesubscriptson d v and N v ,amongothers,whenthecontextisclear. Allgraphsconsideredinthisdissertationaresimple,withnoloopsormultiple edgesbetweenvertices.Thuseachedge e isincidenttoexactlytwodistinctvertices, its endpoints u and v .Additionally,foreverypairofvertices, u and v ,thereisat mostoneedge uv in E Thelistofdegreesoftheverticesofagraph G isthe degreesequence of G .A sequenceofnonnegativeintegers = d 1 ;d 2 ;:::;d n is graphic ifthereisasimple graph G oforder n havingdegreesequence .Inthiscase, G issaidto realize or bea realizationof ,andwewrite = G .Ifasequence consistsoftheterms d 1 ;:::;d t havingmultiplicities 1 ;:::; t ,thenwemaywrite = d 1 1 ;:::;d t t Forthepurposesofthisdissertation,weareofteninterestedinconsideringvarious subgraphs.A subgraph H of G satises V H V G and E H E G .If V H = V G ,then H isa spanning subgraphof G .Aspanning, r -regularsubgraph ofagraph G iscalledan r -factor of G .Ofparticularimportanceforthisdissertation are1-factorsand2-factors.Specically,a1-factorisalsocalleda perfectmatching andisasetofindependentedgesofagraph G whichspanstheverticesof G .A 1

PAGE 12

2-factorofagraph G isasetofdisjointcyclesthatspans G .Asubgraph H of G inwhichforeachpair u and v in V H uv isin E H ifandonlyif uv isin E G isan inducedsubgraph .Agraphon n verticesinwhicheverypossibleedgeappears isa completegraph ,denoted K n .Whenthesubgraphinducedby V H V G formsacompletegraph,wesaythat V H isa clique in G .Ontheotherhand,a subsetof V G containingnoedgesformsan independentset in G .Anindependent setofedgesinagraph G whichdoesnotnecessarilyspan V G isa matching .A path on n vertices,denoted P n isasetofvertices V P n = f v 1 ;:::;v n g withedge set E G = f v i v i +1 : i 2f 1 ;:::;n )]TJ/F15 11.9552 Tf 12.328 0 Td [(1 gg .A cycle oforder n ,denoted C n isapath P n alongwiththeedge v 1 v n .Noticethat K 3 = C 3 ,andwewilloftenrefertothis particularcompletegraphasa triangle .Agraphwithnocyclesisa tree ,andtheset ofdegree1verticesofatreeareits leaves Givenagraph G ,when V G canbepartitionedintotwoindependentsets, X and Y G is bipartite ,andtherefore E G consistsonlyofedges xy where x 2 X and y 2 Y .Forinstance,cyclesonanevennumberofvericesarebipartitegraphs,asare matchingsandtrees.Whenabipartitegraph G containseverypossibleedgebetween X and Y G isa completebipartitegraph ,denoted K n;m ,where j X j = n and j Y j = m Avertexcoloringofagraph G isafunction c : V G !f 1 ;:::;k g .Acoloring isproperifeverypairofadjacentverticesreceivesdistinctcolors,sothatforanyedge uv in E c u 6 = c v .Theminimumnumberofcolorsrequiredtoproperlycolora graph G isthe chromaticnumber of G ,denoted G .Likewise,an edge-coloring of agraph G isafunction c : E G !f 1 ;:::;k g .Anedgecoloringofagraphis proper ifthecolorsonedgessharinganendpointaredistinct,thatisforall v 2 V G c vu 6 = c vw forallvertices u and w in N v .Theminimumnumberofcolors requiredtoproperlyedge-coloragraph G isthe chromaticindex of G denoted 0 G Finally,anedge-coloredgraphis rainbow ifalledgeshavedistinctcolors. Anyundenednotationanddenitionscanbefoundin[87]. 2

PAGE 13

1.2OverviewofStructuralandExtremalGraphTheory Extremalgraphtheoryseekstodeterminemaximumandminimumvaluesof graphparametersthatensureorprohibitparticulargraphproperties.Forinstance, wemayconsiderthethresholdforthenumberofedgesinagraph G whichensures G containssomeparticularsubgraph.The extremalnumber ,denoted ex n;H isthe maximumnumberofedgesinagraph G on n verticessuchthat G doesnotcontaina copyof H .Equivalently,wemayaskhowmanyedgesguaranteethatagraph G on n verticeswithatleast f n edgescontainsacopyof H .In1941,Turan[82]showedthe extremalnumberforcompletegraphson k +1vertices.The Turangraph ,denoted T r n ,isthecomplete r -partitegraphon n vertices,inwhicheachpartisasbalanced aspossible,having j n r k or j n r k +1vertices. Theorem1.1 [82] For r;n 2 ex n;K r +1 = 1 )]TJ/F15 11.9552 Tf 13.151 8.088 Td [(1 r + o n 2 ; and T r n istheuniquegraphthathastheextremalnumberofedgesanddoesnotcontain acopyof K r +1 AsanextensionofTheorem1.1,Erd}osandStone[30]showedthefollowing. Theorem1.2 [30] If G isagraphoforder n withatleast 1 )]TJ/F15 11.9552 Tf 13.469 8.088 Td [(1 k + n 2 2 edges, thenfor n sucientlylarge, G containsacopyofthecomplete k +1 -partitegraph with t verticesineachpart. LaterErd}osandSimonovits[29]gavethegeneralextremalnumberforanygraph H inafamilyofgraph F ,theproofofwhichhighlyreliesuponTheorem1.2. 3

PAGE 14

Theorem1.3 [29] Let F beafamilyofgraphswith p =min f H : H 2Fg ,then ex n; F = 1 )]TJ/F15 11.9552 Tf 23.297 8.088 Td [(1 p +1 n 2 + o n 2 : Structuralgraphtheoryconsidersthesubstructuresofagraph,suchaspaths, cycles,andmatchingsandconsidersconditionsthatguaranteetheexistenceornonexistenceofsuchgraphstructures.Instructuralgraphtheory,thesubstructuresof agrapharethefocus.Theseproblemscanhavetiestoextremalgraphtheory,asin Theorems1.1,1.2,and1.3. Onewaytoensuretheexistenceofparticularsubstructures,suchascycles,isto forbidparticularsubgraphs.Givenafamily F ofgraphs,agraph G issaidtobe F -free if G containsnomemberof F asaninducedsubgraph.Agraph G is perfect ifforeveryinducedsubgraph H of G ,thechromaticnumberof H isequaltothesize ofthelargestcliqueof H .In1961,Berge[6]madetwoconjecturesregardingperfect graphs,whichhavebothbeenshowntobetrue.Theweakerconjecture,thatagraph isperfectifandonlyifitscomplementisperfectwasprovenbyLovaszin1972[65]. In2006,theStrongPerfectGraphTheoremwasprovenbyChudnovsky,Robertson, Seymour,andThomas[14],whichcharacterizesperfectgraphsintermsofforbidden subgraphs. Theorem1.4TheStrongPerfectGraphTheorem [14] Agraph G isperfect ifandonlyif G doesnotcontainaninducedsubgraphwhichisanoddcycleorthe complementofanoddcycle. Structuralandextremalproblemsoftenhaveoverlapinresearch;forinstance knowingthatagraphisbipartiteleadstoanaturalquestionoftheextremalnumber forbipartitegraphs.Theproblemsconsideredherefallintothreemainchapters,and theproblemswewillexplorecanbebroadlyorganizedintostructuralandextremal graphtheory,orsomemixofthese. 4

PAGE 15

InChapter2,wediscussthethresholdforwhenaproperlyedge-coloredgraph G containsaperfectmatchingofsize G .Specically,weansweraquestionposedby Wang[83],ifthereexistsafunction f suchthatif G hasorder n f G then G is guaranteedtocontainarainbowmatchingofsize .Thisproblemhasgainedinterest inpartduetoRyser'sConjecture[75],whichstatesthateveryproperedge-coloring of K 2 k +1 ; 2 k +1 containsarainbowperfectmatching.Thiswasoriginallyformulatedin termsoftransversalsinLatinsquares,andisstillopen.Hereweconsiderproperly edge-coloredgraphsandpresentanalgorithmwhichproducesarainbowmatchingof thedesiredsize, G ,whenthegraphhasenoughverticesrelativetotheminimum degree, G Chapter3discussesthecyclestructureof2-factorsofgraphs,especiallyunderforbiddensubgraphconditions.Togainlocalstructure,weconsider claw-free graphs,thosegraphsthathavetheclaw, K 1 ; 3 ,asaforbiddensubgraph.Wedenoteby h v ; x;y;z i theclawwithcentralvertex v andleaves x y ,and z .In1997, Ryjacek[73]introducedaclosureconceptwhichiterativlyaddsedgestoagraph,and inaclaw-freegraph,eachiterationofthisclosuremaintainsthepropertyofbeing claw-free.Theclosureofaclaw-freegraphalsopreservesthelengthofthelongest cycleandingeneralhasbeenshowntobeausefultoolinstudyingavarietyofstructuralpropertiesofclaw-freegraphs.Wealsodiscussforbiddensubgraphconditionsto ensurethatagraphcontainsa2-factorwithnooddcycles.Inparticular,weconsider forbiddensubgraphsthatguaranteethatagraphcontainsa2-factor,andconsider whatadditionalconditionsensurethatthereisa2-factorwithnooddcycles. InChapter4,wediscussextremalproblemsrelatedtographicsequences.Two n -vertexgraphs G 1 and G 2 pack iftheycanbeexpressedasedge-disjointsubgraphs of K n .SauerandSpencer[76]gaveaclassicresultingraphpacking,thatifthe maximumdegreesof G 1 and G 2 are 1 and 2 respectively,if 1 2 < n 2 then G 1 and G 2 pack.BollobasandEldridge[7]andindependentlyCatlin[12]conjectured 5

PAGE 16

thestrongerconditionthat 1 +1 2 +1 n +1wouldimplythat G 1 and G 2 pack.Thisconjectureremainsopen,butmanypartialresultshavebeenshownto holdseeforexample[1,4,17,55].Weconsideredthegraphicsequenceanalogueto graphpacking.Twographicsequences 1 = d 1 ;:::;d n and 2 = d 1 ;:::;d n pack providedthereareedge-disjointgraphs G 1 and G 2 suchthat d G 1 v i = d i and d G 2 v i = d i ,for i in f 1 ;:::;n g .Ourresultsimplyadegreesequenceanalogueto theBollobas-Eldridge-Catlingraphpackingconjecture[7,12],whichinturnimplies adegreesequenceanaloguetotheSauer-Spencergraphpackingtheorem[76]. 6

PAGE 17

2.RainbowMatchingsinProperlyEdge-ColoredGraphs 2.1Introduction RainbowmatchingsareofparticularinterestgiventheirconnectiontotransversalsofLatinsquares.A Latinsquare oforder n isan n n matrixinwhichasetof n elementsappearsineachrowandineachcolumnsothatnoelementisrepeatedin anyroworcolumn.A transversal inaLatinsquare L isasetof n entriesthatspans therowsandcolumnsof L andcoverseachofthe n distinctelements.EachLatin squarecanbeconvertedtoaproperlyedge-coloredcompletebipartitegraph,anda transversaloftheLatinsquareisarainbowperfectmatchinginthegraph.Specically,let K n;n representaLatinsquare L oforder n whereonepartof K n;n isasetof vertices f 1 R ;:::;n R g foreachrowandtheotherpartisasetofvertices f 1 C ;:::;n C g foreachcolumn.Anedge i R j C receivesacolorcorrespondingtotheelementinthe i;j entryof L .Ryser'sconjecture[75]thateveryLatinsquareofoddorderhasa transversalcanbeseenasthebeginningofthestudyofrainbowmatchings.Stein[79] laterconjecturedthateveryLatinsquareoforder n hasatransversalofsize n )]TJ/F15 11.9552 Tf 12.245 0 Td [(1; equivalentlyeveryproperedge-coloringof K n;n hasarainbowmatchingofsize n )]TJ/F15 11.9552 Tf 11.324 0 Td [(1. TheconnectionbetweenLatintransversalsandrainbowmatchingsin K n;n hasinspiredadditionalinterestinthestudyofrainbowmatchingsintriangle-freegraphs. Athoroughsurveyofrainbowmatchingandotherrainbowsubgraphsinedge-colored graphsappearsin[53]. Severalresultshavebeenattainedforrainbowmatchingsinarbitrarilyedgecoloredgraphs.The colordegree ofavertex v inanedge-coloredgraph G ,written ^ d v ,isthenumberofdistinctcolorsonedgesincidentto v .Welet ^ G denotethe minimumcolordegreeamongtheverticesin G .WangandLi[84]provedthatevery edge-coloredgraph G containsarainbowmatchingofsizeatleast l 5 ^ G )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 12 m ,and conjecturedthatarainbowmatchingofsize l ^ G 2 m existsif ^ G 4.LeSaulnieret al.[62]thenprovedthateveryedge-coloredgraph G containsarainbowmatchingof 7

PAGE 18

size j ^ G 2 k .Finally,KostochkaandYancey[59]provedtheconjectureofWangand Liinfull,andalsoprovedthattriangle-freegraphshaverainbowmatchingsofsize l 2 ^ G 3 m Sincetheedge-coloredgraphsgeneratedbyLatinsquaresareproperlyedgecolored,itisofinteresttoconsiderrainbowmatchingsinproperlyedge-coloredgraphs. Inthisdirection,LeSaulnieretal.[62]provedthataproperlyedge-coloredgraph G satisfying j V G j6 = G +2thatisnot K 4 hasarainbowmatchingofsize l G 2 m Wangthenaskedifthereisafunction f suchthataproperlyedge-coloredgraph G withminimumdegree andorderatleast f mustcontainarainbowmatching ofsize [83].Asarststeptowardsansweringthisquestion,Wangshowedthata graph G withorderatleast8 = 5hasarainbowmatchingofsize j 3 G 5 k Sincethereare n n Latinsquareswithnotransversalswhen n isevensee[9,86], forsuchafunction f itisclearthat f > 2 when iseven.Furthermore,sincea maximummatchingin K ;n )]TJ/F20 7.9701 Tf 6.586 0 Td [( hasonly edgesprovided n 2 ,thereisnofunction fortheorderof G dependingon G thatcanguaranteearainbowmatchingofsize greaterthan G InthischapterweanswerWang'squestionfrom[83]inthearmative,proving thatalinearnumberofverticesintermsoftheminimumdegreesuces. Theorem2.1 [21] If G isaproperlyedge-coloredgraphsatisfying j V G j 98 G 23 ; then G containsarainbowmatchingofsize G Independently,Wang,Zhang,andLiu[85]alsoansweringWang'squestioninthe armative,provedthataproperlyedge-coloredgraph G withatleast 1 4 G 2 + 4 G )]TJ/F15 11.9552 Tf 11.955 0 Td [(4verticeshasarainbowmatchingofsize G TheproofofTheorem2.1utilizesextremaltechniquesakintothosethatappear 8

PAGE 19

in[59,62,83]and[84].Wealsoimplementagreedyalgorithmicapproachtodemonstratethatitispossibletoecientlyconstructarainbowmatchingofsize ina properlyedge-coloredgraphwithminimumdegree havingorderatleast6 : 5 .To ourknowledge,analgorithmicapproachofthistypehasnotbeenpreviouslyemployed inthestudyofrainbowmatchings. Theorem2.2 [21] If G isaproperlyedge-coloredgraphwithminimumdegree satisfying j V G j > 13 2 )]TJ/F15 11.9552 Tf 13.151 8.088 Td [(23 2 + 41 8 ; thenthereisan O G j V G j 2 -timealgorithmthatproducesarainbowmatchingof size in G Asacontrast,Itai,Rodeh,andTanimota[52]provedthatdeterminingifan edge-coloredgraph G hasarainbowmatchingofsize k isNP-complete,evenif G isbipartite.Morerecently,LeandPfender[61]haveshownthattheproblemof determiningthemaximumsizeofarainbowmatchinginaproperlyedge-colored graphisNP-hard,evenwhenrestrictedtoproperlyedge-coloredpaths. 2.2ProofofTheorem2.1 Let G beaproperlyedge-colored n -vertexgraphwithminimumdegree and n 98 23 .Thetheoremholdseasilyif 2,sowemayassumethat 3.Bywayof contradiction,let G beacounterexamplewith minimized;thus G doesnotcontain arainbowmatchingofsize .Further,wemayassumethat j E G j isminimized,soin particulartheverticesofdegreegreaterthan formanindependentset,asotherwise wecoulddeleteanedgewithoutloweringtheminimumdegree.Webreaktheproof intoaseriesofsimpleclaims. Let G = d 1 d 2 ::: d n = with d v i = d i bethedegreesequenceof G Lemma2.3 For 1 k 2 = 3 ,thereexistsan i k suchthat d i 3 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k )]TJ/F15 11.9552 Tf 11.956 0 Td [(2 i 9

PAGE 20

Proof: Supposethatforsome k 2 = 3, d i 3 +1 )]TJ/F19 11.9552 Tf 12.115 0 Td [(k )]TJ/F15 11.9552 Tf 12.116 0 Td [(2 i forall1 i k .It followsthat d i > for i k ,andtherefore f v 1 ;:::;v k g isanindependentset.Delete thevertices v 1 ;v 2 ;:::;v k from G ,andnotethat G nf v 1 ;:::;v k g )]TJ/F19 11.9552 Tf 12.105 0 Td [(k .Bythe minimalityof G ,thereexistsarainbowmatching M k ofsize )]TJ/F19 11.9552 Tf 11.2 0 Td [(k in G nf v 1 ;:::;v k g Thevertex v k hasatmost2 )]TJ/F19 11.9552 Tf 12.172 0 Td [(k neighborsin M k ,andisincidenttoatmost )]TJ/F19 11.9552 Tf 10.72 0 Td [(k edgescoloredwithcolorsoccurringin M k .Thus, v k hasaneighbor w k = 2 V M k suchthatthecolorof v k w k doesnotoccurin M k ,andwecanextend M k byadding theedge v k w k ;calltheresultingrainbowmatching M k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Notethat w k 6 = v i for i k as f v 1 ;:::v k g isanindependentset. The j thiterationofthisprocessproducesarainbowmatching M k )]TJ/F20 7.9701 Tf 6.587 0 Td [(j ofsize )]TJ/F19 11.9552 Tf 9.539 0 Td [(k + j thatcontains f v k ;:::;v k )]TJ/F20 7.9701 Tf 6.587 0 Td [(j +1 g .Hence v k )]TJ/F20 7.9701 Tf 6.586 0 Td [(j hasatmost2 )]TJ/F19 11.9552 Tf 10.697 0 Td [(k + j neighborsin M k )]TJ/F20 7.9701 Tf 6.587 0 Td [(j andisincidenttoatmost )]TJ/F19 11.9552 Tf 12.736 0 Td [(k + j edgescoloredwithcolorsoccurringin M k )]TJ/F20 7.9701 Tf 6.586 0 Td [(j Thusthereisavertex w k )]TJ/F20 7.9701 Tf 6.587 0 Td [(j 2 N v k )]TJ/F20 7.9701 Tf 6.587 0 Td [(j suchthattheedge v k )]TJ/F20 7.9701 Tf 6.586 0 Td [(j w k )]TJ/F20 7.9701 Tf 6.586 0 Td [(j extends M k )]TJ/F20 7.9701 Tf 6.587 0 Td [(j to a )]TJ/F19 11.9552 Tf 11.11 0 Td [(k + j +1-edgerainbowmatching M k )]TJ/F17 7.9701 Tf 6.587 0 Td [( j +1 .Continuinginthisfashionextends thematching M k by k edges,yieldingarainbowmatchingofsize ,acontradiction nishingtheproof. AsacorollaryofLemma2.3,weobtainthefollowing. Lemma2.4 For 1 k 2 = 3 ,wehave P k i =1 d i k )]TJ/F15 11.9552 Tf 11.957 0 Td [(2 )]TJ/F19 11.9552 Tf 11.957 0 Td [(k ,withequalityonly if d 1 = d k =3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k Proof: Weproceedbyinductionon k .For k =1,thestatementfollowsfrom Lemma2.3.Nowlet k> 1andlet i k suchthat d i 3 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 i .Byinduction, i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 X j =1 d j i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(i ; and k X j = i d j k )]TJ/F19 11.9552 Tf 11.955 0 Td [(i +1 d i k )]TJ/F19 11.9552 Tf 11.955 0 Td [(i +1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 i : 10

PAGE 21

Thus, k X j =1 d j i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(i + k )]TJ/F19 11.9552 Tf 11.955 0 Td [(i +1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k )]TJ/F15 11.9552 Tf 11.956 0 Td [(2 i =3 k )]TJ/F19 11.9552 Tf 11.955 0 Td [(k 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k +1 )]TJ/F19 11.9552 Tf 11.956 0 Td [(i k +2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(i k )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k andequalityholdsonlyif i =1and d 1 = d k =3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k Let C beamaximumcolorclassin G andlet j C j = a .Bytheminimalityof G thereexistsarainbowmatching M = f x i y i :1 i )]TJ/F15 11.9552 Tf 12.149 0 Td [(1 g ofsize )]TJ/F15 11.9552 Tf 12.149 0 Td [(1in G )]TJ/F19 11.9552 Tf 12.15 0 Td [(C Withoutlossofgenerality,wemayassumethat c x i y i = i for1 i )]TJ/F15 11.9552 Tf 11.837 0 Td [(1andthe edgesin C havecolor .Let W = V G n V M ;observethat j W j = n )]TJ/F15 11.9552 Tf 12.413 0 Td [(2 )]TJ/F15 11.9552 Tf 12.413 0 Td [(1. Ifthereisanedge e in G [ W ]with c e = 2f 1 ;:::; )]TJ/F15 11.9552 Tf 12.17 0 Td [(1 g thenwecanadd e to M to obtainarainbowmatchingofsize .Thuswemayassumethateveryedgewhose colorisnotin f 1 ;:::; )]TJ/F15 11.9552 Tf 11.149 0 Td [(1 g hasanendpointin V M .Anedge uv is good ifitscolor isnotin f 1 ;:::; )]TJ/F15 11.9552 Tf 11.961 0 Td [(1 g andoneofitsendpointsisin W .Avertex v 2 V M is good if v isincidentwithatleastsevengoodedges. Claim2.5 For i 2f 1 ;:::; )]TJ/F15 11.9552 Tf 10.732 0 Td [(1 g ,if x i isincidentwithatleastthreegoodedges,then nogoodedgeisincidentwith y i ,andviceversa. Proof: Supposethat y i u isagoodedge.If x i isincidentwithatleastthree goodedges,then x hasaneighbor w suchthat vw isagoodedge, w 6 = u ,and c x i w 6 = c y i u .Thus M [f x i w;y i u g nf x i y i g isarainbowmatchingofsize ,a contradiction. ByClaim2.5,wemayassumewithoutlossofgeneralitythat f x 1 ;:::;x r g isthe setofgoodverticesforsome r 0.Let W 0 = W [f y 1 ;:::;y r g Claim2.6 Noedge uv in G [ W 0 ] hascolorin f 1 ;:::;r g Proof: Bywayofcontradiction,assumethatthereisanedge uv in G [ W 0 ] 11

PAGE 22

suchthat c uv 2f 1 ;:::;r g .Let M 0 bethesubsetof M consistingoftheedgewith color c uv andanyedgeswithanendpointin f u;v g .Thereareatmostthreesuch edgestheedgewithcolor c uv andpossiblyoneforeachendpoint;withoutloss ofgenerality,let M 0 = f x 1 y 1 ;:::;x t y t g here1 t 3.Notethat x j isagood vertexfor1 j t .Thustherearedistinctvertices w 1 ;:::;w t suchthat x j w j isa goodedgefor1 j t andthecolorsontheedges uv;x 1 w 1 ;:::;x t w t aredistinct. Thus M [f uv;x 1 w 1 ;:::;x t w t g nf x 1 y 1 ;:::;x t y t g isarainbowmatchingofsize ,a contradiction. Anedge uv is nice ifitscolorisnotin f r +1 ;:::; )]TJ/F15 11.9552 Tf 10.407 0 Td [(1 g andoneofitsendpointsis in W 0 .Notethateverygoodedgeisnice.Recallthateverygoodedgehasanendpoint in V M .ByClaim2.5andClaim2.6,noniceedgeliesin G [ W 0 ].Hence,everynice edgejoinsverticesin W 0 and V G n W 0 .Avertex v 2 V M nf x 1 ;:::;x r ;y 1 ;:::;y r g is nice if v isincidentwithatleastsevenniceedges.Notethatifthereisnogood vertexi.e. r =0,thenthedenitionsofgoodandniceverticesarethesameandso thereisalsononicevertex.Next,weproveanaloguesofClaim2.5andClaim2.6for niceverticesandedges. Claim2.7 For i 2f r +1 ;:::; )]TJ/F15 11.9552 Tf 11.836 0 Td [(1 g ,if x i isincidentwithatleastthreeniceedges, thennoniceedgeisincidentwith y i ,andviceversa. Proof: Suppose y i u isaniceedgeforsome i 2f r +1 ;:::; )]TJ/F15 11.9552 Tf 12.806 0 Td [(1 g .If x i is incidenttoatleastthreeniceedges,then x i hasaneighbor v suchthat x i v isanice edge, v 6 = u ,and c x i v 6 = c y i u .Let M 0 bethesubsetof M consistingofedges withanendpointin f u;v g oracolorin f c x i v ;c y i u g .Thereareatmostfoursuch edgespossiblyonewitheachendpointandonewitheachcolor;withoutlossof generality,let M 0 = f x 1 y 1 ;:::;x t y t g here0 t 4.Notethat x j isagoodvertex for1 j t .Thustherearedistinctvertices w 1 ;:::;w t suchthat x j w j isagood edgefor1 j t andthecolorsontheedges x i v;y i u;x 1 w 1 ;:::;x t w t aredistinct. 12

PAGE 23

Thus M [f x i v;y i u;x 1 w 1 ;:::;x t w t g nf x i y i ;x 1 y 1 ;:::;x t y t g isarainbowmatchingof size ,acontradiction. ByClaim2.7,wemayassumethat f x r +1 ;x r +2 ;:::;x r + s g isthesetofnicevertices forsome s 0. Claim2.8 Noedge uv in G [ W 0 ] hascolorin f 1 ;:::;r + s g Proof: ByClaim2.6,theclaimholdsif s =0.Assumethat s 1,and consequently r 1.Withoutlossofgenerality,supposethatthereisanedge uv in G [ W 0 ]with c uw = r +1.Because x r +1 isnice,ithasaneighbor v 0 in W 0 suchthat x r +1 v 0 isaniceedgeand v 0 6 = u;v .Let M 0 bethesubsetof M consistingofthoseedges withanendpointin f u;v;v 0 g orcolor c x r +1 v 0 .Againthereareatmostfouredges in M 0 andwelet M 0 = f x 1 y 1 ;:::;x t y t g .Asbefore, w 1 ;:::;w t aredistinctvertices suchthat x j w j isagoodedgefor1 j t andthecolorson uv x 1 w 1 ;:::;x t w t aredistinct,thus M [f uv;x r +1 v 0 ;x 1 w 1 ;:::;x t w t g nf x r +1 y r +1 ;x 1 y 1 ;:::;x t y t g isa rainbowmatchingofsize ,acontradiction. Next,wecountthenumberofniceedgesin G Claim2.9 Thereareatmost max )]TJ/F15 11.9552 Tf 11.955 0 Td [(8 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r + s r +6 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; 7 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(7+ s r +6 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 niceedgesin G Proof: Recallthat V G n W 0 = f x 1 ;:::;x )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;y r +1 ;:::;y )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 g andeverynice edgejoinsverticesfrom W 0 and V G n W 0 .If r 2 = 3,thenthesetofgoodvertices isincidenttoatmost r )]TJ/F15 11.9552 Tf 11.957 0 Td [(2 )]TJ/F19 11.9552 Tf 11.957 0 Td [(r niceedgesbyLemma2.4.Similarly,if r 2 = 3, thenthesetofgoodverticesisincidenttoatmost r )]TJ/F15 11.9552 Tf 11.922 0 Td [(2 )-219(b 2 = 3 c r = 3 )]TJ/F15 11.9552 Tf 11.922 0 Td [(1 niceedges.For i 2f r +1 ;:::;r + s g ,Claim2.7impliesthat x i isincidenttoatmost r +6niceedgesand y i isincidenttonone.For i 2f r + s +1 ;:::; )]TJ/F15 11.9552 Tf 10.914 0 Td [(1 g ,byClaim2.7 13

PAGE 24

thereareatmostsixniceedgeswithanendpointin f x i ;y i g .Therefore,thenumber ofniceedgesisatmost )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r r + r +6 s +6 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r )]TJ/F19 11.9552 Tf 11.955 0 Td [(s = )]TJ/F15 11.9552 Tf 11.955 0 Td [(8 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r + s r +6 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 if r 2 = 3,and 7 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 r + r +6 s +6 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r )]TJ/F19 11.9552 Tf 11.956 0 Td [(s = 7 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(7+ s r +6 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 if r 2 = 3. Recallthat C isthecolorclasswithcolor j C j = a ,and C isamaximumsize colorclass.Thereforethereareatleast2 a )]TJ/F19 11.9552 Tf 11.129 0 Td [( +1verticesin W incidenttoanedge in C .Sinceeveryedgein C hasanendpointin V M itfollowsthatthereareatleast 2 a )]TJ/F19 11.9552 Tf 11.561 0 Td [( +1verticesin V M joinedto W byedgesin C .Withoutlossofgenerality, let f r + s +1 ;:::;r + s + t g bethesetofindices i 2f r + s +1 ;:::; )]TJ/F15 11.9552 Tf 11.762 0 Td [(1 g suchthat x i or y i isincidenttoanedgein C .ByClaim2.5andClaim2.7,wehave t a )]TJ/F19 11.9552 Tf 11.955 0 Td [( +1 )]TJ/F19 11.9552 Tf 13.15 8.088 Td [(r + s 2 and r + s + t )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : .1 Claim2.10 For i 2f r + s +1 ;:::;r + s + t g ,thereisatmostoneedgeofcolor i in G [ W ] Proof: Suppose uv and u 0 v 0 areedgesofcolor i in G [ W ]forsome i 2f r + s + 1 ;:::;r + s + t g .Withoutlossofgenerality,wemayassumethatthereexists w 2 W suchthat c x i w = and w 6 = u;v .Hence, M [f uv;x i w g nf x i y i g isarainbow matchingofsize ,acontradiction. Nowwecountthenumberofniceedgesfrom W 0 to V G n W 0 .Recallthateach colorclassin G containsatmost a edges.ByClaim2.8,thereisnoedgein G [ W 0 ]of color i 2f r +1 ;:::;r + s g .Thus,for i 2f r +1 ;:::;r + s g thereareatmost a )]TJ/F15 11.9552 Tf 12.088 0 Td [(1 14

PAGE 25

verticesin W 0 thatareincidentwithanedgeofcolor i .Sinceeverycolorclasshassize atmost a ,for i 2f r + s +1 ;:::; )]TJ/F15 11.9552 Tf 9.991 0 Td [(1 g thereareatmost2 a )]TJ/F15 11.9552 Tf 9.991 0 Td [(1verticesin W 0 thatare incidentwithanedgeofcolor i .Furthermorefor i 2f r + s +1 ;:::;r + s + t g ,Claim2.10 impliesthatthereareatmost a verticesin W thatareincidentwithanedgeofcolor i Since W 0 n W = f y 1 ;:::;y r g ,itfollowsthatfor i 2f r + s +1 ;:::;r + s + t g thereare atmostmin f a + r; 2 a )]TJ/F15 11.9552 Tf 11.748 0 Td [(1 g verticesin W 0 thatareincidentwithanedgeofcolor i Itthenfollows,usingthefactthat j W 0 j = j W j + r = n )]TJ/F15 11.9552 Tf 11.701 0 Td [(2 )]TJ/F15 11.9552 Tf 11.701 0 Td [(1+ r and.1,that thenumberofniceedgesfrom W 0 to V G n W 0 isatleast j W 0 j)]TJ/F15 11.9552 Tf 17.933 0 Td [( a )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 r )]TJ/F19 11.9552 Tf 11.955 0 Td [(s )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 t )]TJ/F15 11.9552 Tf 11.955 0 Td [(min f a + r; 2 a )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 g t = n )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ r )]TJ/F15 11.9552 Tf 11.956 0 Td [( a )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 r )]TJ/F19 11.9552 Tf 11.955 0 Td [(s +max f a )]TJ/F19 11.9552 Tf 11.955 0 Td [(r )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 ; 0 g t: Werstconsiderthecasewhen r 2 = 3.Applyingtheupperboundof )]TJ/F15 11.9552 Tf -422.702 -23.98 Td [(8 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r + s r +6 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1niceedgesfromClaim2.9,weobtain n )]TJ/F15 11.9552 Tf 11.955 0 Td [(8 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r + s r +2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ a )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 r )]TJ/F19 11.9552 Tf 11.956 0 Td [(s )]TJ/F15 11.9552 Tf 11.291 0 Td [(max f a )]TJ/F19 11.9552 Tf 11.955 0 Td [(r )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 ; 0 g t: .2 Tonishtheproofweboundtherighthandsideof.2toobtainacontradiction. Notethatthecoecientof t isnonpositive.Thus,therighthandsideof.2is maximizedwhen t isminimized.By.1, t max f a )]TJ/F19 11.9552 Tf 11.955 0 Td [( +1 )]TJ/F15 11.9552 Tf 11.955 0 Td [( r + s = 2 ; 0 g If a )]TJ/F15 11.9552 Tf 10.858 0 Td [(1+ r + s = 2,thenwelet t =0.Thecoecientof a isnonnegative,and thus.2ismaximizedwhen a ismaximized;henceweassume a = )]TJ/F15 11.9552 Tf 11.149 0 Td [(1+ r + s = 2. Substitutingfor a yieldsanegativequadraticin s thatismaximizedwhen s =1 )]TJ/F19 11.9552 Tf 10.033 0 Td [(r= 2. Since s isanonnegativeintegerand s =0if r =0,.2ismaximizedat s =0,which 15

PAGE 26

yields n 2 +1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ )]TJ/F15 11.9552 Tf 11.955 0 Td [(5 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 r r: Thisismaximizedwhen r = )]TJ/F15 11.9552 Tf 11.955 0 Td [(5 = 4,yielding n 33 8 )]TJ/F17 7.9701 Tf 13.151 4.707 Td [(13 4 + 9 8 ,acontradiction. If a> )]TJ/F15 11.9552 Tf 12.827 0 Td [(1+ r= 2,welet t = a )]TJ/F19 11.9552 Tf 12.828 0 Td [( +1 )]TJ/F19 11.9552 Tf 12.827 0 Td [(r= 2.Since t> 0,itfollowsthat r + s )]TJ/F15 11.9552 Tf 12.293 0 Td [(2.Thus a )]TJ/F19 11.9552 Tf 12.293 0 Td [(r )]TJ/F15 11.9552 Tf 12.292 0 Td [(2 > )]TJ/F15 11.9552 Tf 12.292 0 Td [(3 )]TJ/F15 11.9552 Tf 12.292 0 Td [( r )]TJ/F19 11.9552 Tf 12.292 0 Td [(s = 2 )]TJ/F15 11.9552 Tf 12.292 0 Td [(3 )]TJ/F15 11.9552 Tf 12.293 0 Td [( )]TJ/F15 11.9552 Tf 12.292 0 Td [(2 = 2= = 2 )]TJ/F15 11.9552 Tf 12.292 0 Td [(2. As 3and a )]TJ/F19 11.9552 Tf 12.163 0 Td [(r )]TJ/F15 11.9552 Tf 12.162 0 Td [(2isaninteger,max f a )]TJ/F19 11.9552 Tf 12.162 0 Td [(r )]TJ/F15 11.9552 Tf 12.162 0 Td [(2 ; 0 g = a )]TJ/F19 11.9552 Tf 12.162 0 Td [(r )]TJ/F15 11.9552 Tf 12.162 0 Td [(2.Thereforethe coecientof s in.2isnonpositiveandwemayassumethat s =0.Consequently, .2becomes n )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r= 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(a a + )]TJ/F15 11.9552 Tf 11.955 0 Td [(6 )]TJ/F15 11.9552 Tf 11.955 0 Td [(3 r= 2 r +2 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : Therighthandsideismaximizedwhen a = 3 2 )]TJ/F17 7.9701 Tf 13.151 4.707 Td [(1 2 )]TJ/F20 7.9701 Tf 13.239 4.707 Td [(r 4 ,so n 1 16 )]TJ/F15 11.9552 Tf 9.299 0 Td [(28+68 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(24 +4 r )]TJ/F15 11.9552 Tf 11.955 0 Td [(92 r )]TJ/F15 11.9552 Tf 11.955 0 Td [(23 r 2 ; whichismaximizedwhen r =2 = 23 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2.Thisyields n 98 23 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2+ 4 ; acontradiction. Tocompletetheproofofthetheorem,weareleftwiththecase r 2 = 3.Similar to.2,sincewehaveatmost = 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(7+ s r +6 )]TJ/F15 11.9552 Tf 10.082 0 Td [(1niceedgesin G byClaim2.9, wehave n = 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(7+ s r +2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ a )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 )]TJ/F15 11.9552 Tf 11.956 0 Td [(2 r )]TJ/F19 11.9552 Tf 11.955 0 Td [(s )]TJ/F15 11.9552 Tf 11.955 0 Td [(max f a )]TJ/F19 11.9552 Tf 11.955 0 Td [(r )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 ; 0 g t: .3 16

PAGE 27

Again,therighthandsideof.3ismaximizedwhen t isminimized. If a )]TJ/F15 11.9552 Tf 11.42 0 Td [(1+ r + s = 2,then.3ismaximizedwhen t =0and a = )]TJ/F15 11.9552 Tf 11.419 0 Td [(1+ r= 2. Againwemayassumethat s =0,yielding n )]TJ/F15 11.9552 Tf 23.91 0 Td [(2+4 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 + r 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(4 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r : Thisismaximizedwhen r = = 6 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2,yielding n 145 36 )]TJ/F17 7.9701 Tf 13.151 4.707 Td [(8 3 + 6 ,acontradiction. If a> )]TJ/F15 11.9552 Tf 11.138 0 Td [(1+ r + s = 2,welet t = a )]TJ/F19 11.9552 Tf 11.138 0 Td [( +1 )]TJ/F15 11.9552 Tf 11.138 0 Td [( r + s = 2andagainwemayassume that s =0.Then,.3becomes n 1 6 )]TJ/F22 11.9552 Tf 5.48 -9.684 Td [()]TJ/F15 11.9552 Tf 9.298 0 Td [(6 a 2 +3 a )]TJ/F15 11.9552 Tf 11.955 0 Td [(2+12 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [( a +30+3 r )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 r )]TJ/F15 11.9552 Tf 11.955 0 Td [(12 ; whichismaximizedwhen r isminimized.Sincewehaveassumedthat r 2 = 3, wehave r =2 = 3andwearebackinthecase r 2 = 3,nishingtheproofofthe theorem. 2.3ProofofTheorem2.2 Weproceedbyinductionon G .Theresultistrivialif G =1.Weassume that G isagraphwithminimumdegree > 1andordergreaterthan 13 2 )]TJ/F17 7.9701 Tf 13.151 4.707 Td [(23 2 + 41 8 Lemma2.11 If G hasacolorclasscontainingatleast 2 )]TJ/F15 11.9552 Tf 12.266 0 Td [(1 edges,then G hasa rainbowmatchingofsize Proof: Let C beacolorclasswithatleast2 )]TJ/F15 11.9552 Tf 11.656 0 Td [(1edges.Byinduction,thereis arainbowmatching M ofsize )]TJ/F15 11.9552 Tf 12.079 0 Td [(1in G )]TJ/F19 11.9552 Tf 12.079 0 Td [(C .Thereare2 )]TJ/F15 11.9552 Tf 12.079 0 Td [(2verticescoveredby theedgesin M ,thusoneoftheedgesin C hasnoendpointcoveredby M ,andthe matchingcanbeextended. Itisusefultonotethatwealsohavethefollowing,whichisidenticaltoLemma 2.3when k =1. 17

PAGE 28

Lemma2.12 If G satises G > 3 )]TJ/F15 11.9552 Tf 12.176 0 Td [(3 ,then G hasarainbowmatchingofsize Webeginbypreprocessingthegraphsothateachedgeisincidenttoatleastone vertexwithdegree .Toachievethis,arbitrarilyordertheedgesin G andprocess theminorder.Ifbothendpointsofanedgehavedegreegreaterthan whenitis processed,deletethatedge.Intheresultinggraph,everyedgeisincidenttoavertex withdegree .Furthermore,byLemma2.12wemayassumethat G 3 )]TJ/F15 11.9552 Tf 12.461 0 Td [(3; thusthedegreesumoftheendpointsofanyedgeisboundedaboveby4 )]TJ/F15 11.9552 Tf 11.937 0 Td [(3.After preprocessing,webeginthegreedyalgorithm. Inthe i thstepofthealgorithm,asmallestcolorclassischosenwithoutloss ofgenerality,color i ,andthenanedge e i ofcolor i ischosensuchthatthedegree sumoftheendpointsisminimized.Alltheremainingedgesofcolor i andalledges incidentwiththeendpointsof e i aredeleted.Thealgorithmterminateswhenthere arenoedgesinthegraph. Weassumethatthealgorithmfailstoproduceamatchingofsize in G ;suppose thattherainbowmatching M generatedbythealgorithmhassize k .Welet R denote thesetofverticesthatarenotcoveredby M Let c i denotethesizeofthesmallestcolorclassatstep i .Sinceatmosttwo edgesofcolor i +1aredeletedinstep i oneateachendpointof e i ,weobservethat c i +1 +2 c i .Otherwise,atstep i colorclass i +1hasfeweredges.Letstep h be thelaststepinthealgorithminwhichacolorclassthatdoesnotappearin M is completelyremovedfrom G .Itthenfollowsthat c h 2,andingeneral c i 2 h )]TJ/F19 11.9552 Tf 9.537 0 Td [(i +1 for i 2 [ h ].Let f i denotethenumberofedgesofcolor i deletedinstep i withboth endpointsin R .Since f i h ,thedegreesumoftheendpoints 18

PAGE 29

of e i isatmost2 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1. For i 2 [ h ],let x i and y i betheendpointsof e i ,andlet d i v denotethedegreeof avertex v atthebeginningofstep i .Let i =max f 0 ;d i x i + d i y i )]TJ/F15 11.9552 Tf 11.604 0 Td [(2 g ;notethat 2 2 + i 4 )]TJ/F15 11.9552 Tf 10.906 0 Td [(3.Thus,atstep i ,atmost2 + i + f i )]TJ/F15 11.9552 Tf 10.906 0 Td [(1edgesareremovedfrom thegraph.Sincethealgorithmremoveseveryedgefromthegraph,weconcludethat j E G j k )]TJ/F19 11.9552 Tf 11.955 0 Td [(h )]TJ/F15 11.9552 Tf 11.955 0 Td [(2+ h X i =1 + i + f i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : .4 Wenowcomputealowerboundforthenumberofedgesin G .Sincethedegree sumoftheendpointsof e i in G isatleast2 + i ,weimmediatelyobtainthefollowing inequality: n + P i 2 [ h ] i 2 j E G j : If f i > 0and i > 0,thenthereisanedgewithcolor i havingbothendpointsin R .Sincethisedgewasnotchoseninstep i bythealgorithm,thedegreesumofits endpointsisatleast2 + i ,andoneofitsendpointshasdegreeatleast + i .For eachvalueof i satisfying f i > 0,wewishtochoosearepresentativevertexin R with degreeatleast + i .Sincethereare f i edgeswithcolor i havingbothendpoints in R ,thereare f i possiblerepresentativesforcolor i .Sinceavertexin R withhigh degreemaybetherepresentativeformultiplecolors,wewishtoselectthelargest systemofdistinctrepresentatives. Supposethatthelargestsystemofdistinctrepresentativeshassize t ,andlet T bethesetofindicesofthecolorsthathaverepresentatives.Foreachcolor i 2 T thereisadistinctvertexin R withdegreeatleast + i .Thuswemayincreasethe edgecountof G asfollows: n + P i 2 [ h ] i + P i 2 T i 2 j E G j : .5 Welet f f # i g denotethesequence f f i g i 2 [ h ] sortedinnonincreasingorder.Since 19

PAGE 30

f i 2 h )]TJ/F19 11.9552 Tf 11.976 0 Td [(i +1,weconcludethat f # i 2 h )]TJ/F19 11.9552 Tf 11.976 0 Td [(i +1.Becausethereisnosystemof distinctrepresentativesofsize t +1,thesequence f f # i g cannotmajorizethesequence f t +1 ;t;t )]TJ/F15 11.9552 Tf 9.966 0 Td [(1 ;:::; 1 g .Hencethereisasmallestvalue p 2 [ t +1]suchthat f # p t +1 )]TJ/F19 11.9552 Tf 9.966 0 Td [(p Therefore,themaximumvalueof P h i =1 f # i isboundedbythesumofthesequence f 2 h )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; 2 h )]TJ/F15 11.9552 Tf 11.956 0 Td [(3 ;:::; 2 h )]TJ/F19 11.9552 Tf 11.955 0 Td [(p +3 ;t +1 )]TJ/F19 11.9552 Tf 11.956 0 Td [(p;:::;t +1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(p g .Summingweattain X i 2 [ h ] f i p )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h )]TJ/F19 11.9552 Tf 11.955 0 Td [(p +1+ h )]TJ/F19 11.9552 Tf 11.955 0 Td [(p +1 t +1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(p : Over p ,thisvalueismaximizedwhen p = t +1,yielding P i 2 [ h ] f i t h )]TJ/F19 11.9552 Tf 11.978 0 Td [(t .Since h )]TJ/F15 11.9552 Tf 11.955 0 Td [(1,wethenhave P i 2 [ h ] f i 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 t )]TJ/F19 11.9552 Tf 11.955 0 Td [(t 2 Wenowcombinebounds.4and.5: n + P i 2 [ h ] i + P i 2 T i 2 k )]TJ/F19 11.9552 Tf 11.955 0 Td [(h )]TJ/F15 11.9552 Tf 11.955 0 Td [(2+ h X i =1 + i + f i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : Hence,since k )]TJ/F15 11.9552 Tf 11.955 0 Td [(1, n 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1+ 1 2 X [ h ] n T i + X i 2 [ h ] f i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t )]TJ/F15 11.9552 Tf 11.956 0 Td [(3 = 2+2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 t )]TJ/F19 11.9552 Tf 11.955 0 Td [(t 2 3 2 )]TJ/F15 11.9552 Tf 13.151 8.087 Td [(11 2 + 5 2 + )]TJ/F15 11.9552 Tf 13.151 8.087 Td [(1 2 t )]TJ/F19 11.9552 Tf 11.955 0 Td [(t 2 : Thisboundismaximizedwhen t = )]TJ/F17 7.9701 Tf 13.151 4.707 Td [(1 2 = 2.Thus n 13 2 )]TJ/F15 11.9552 Tf 13.15 8.088 Td [(23 2 + 41 8 ; contradictingourchoicefortheorderof G Itremainstoshowthatthisproofprovidestheframeworkofa O G j V G j 2 timealgorithmthatgeneratesarainbowmatchingofsize G inaproperlyedgecoloredgraph G oforderatleast 13 2 )]TJ/F17 7.9701 Tf 13.749 4.707 Td [(23 2 + 41 8 .Givensuchagraph G ,wecreate 20

PAGE 31

asequenceofgraphs f G i g asfollows,letting G = G 0 = G ,and n = j V G j First,determine G i G i ,andthemaximumsizeofacolorclassin G i ;this processtakes O n 2 -time.If G i 3 G i )]TJ/F15 11.9552 Tf 13.235 0 Td [(3andthemaximumcolorclass hasatmost2 G i )]TJ/F15 11.9552 Tf 13.018 0 Td [(2edges,thenterminatethesequenceandset G i = G 0 .If G i > 3 G i )]TJ/F15 11.9552 Tf 11.627 0 Td [(3,thendeleteavertex v ofmaximumdegreeandthenprocessthe edgesof G i )]TJ/F19 11.9552 Tf 11.018 0 Td [(v ,iterativelydeletingthosewithtwoendpointsofdegreeatleast G i ; theresultinggraphis G i +1 .If G i 3 G i )]TJ/F15 11.9552 Tf 12.644 0 Td [(3butamaximumcolorclass C hasatleast2 G i )]TJ/F15 11.9552 Tf 12.318 0 Td [(1edges,thendelete C andthenprocesstheedgesof G i )]TJ/F19 11.9552 Tf 12.318 0 Td [(C iterativelydeletingthosewithtwoendpointsofdegreeatleast G i ;theresulting graphis G i +1 .Notethat G i +1 = G i )]TJ/F15 11.9552 Tf 12.345 0 Td [(1.Ifthisprocessgenerates G ,weset G 0 = G andterminate.Generatingthesequence f G i g consistsofatmost steps, eachtaking O n 2 -time. Giventhat G 0 = G i ,thealgorithmfromtheproofofTheorem2.2takes O n 2 timetogenerateamatchingofsize )]TJ/F19 11.9552 Tf 12.94 0 Td [(i in G 0 .Thepreprocessingstepandthe processofdeterminingasmallestcolorclassandchoosinganedgeinthatclasswhose endpointshaveminimumdegreesumbothtake O n 2 -time.Thisprocessisrepeated atmost times. Amatchingofsize )]TJ/F15 11.9552 Tf 12.153 0 Td [( i +1in G i +1 iseasilyextendedin G i toamatchingof size )]TJ/F19 11.9552 Tf 11.979 0 Td [(i usingthevertexofmaximumdegreeormaximumcolorclass.Theprocess ofextendingthematchingtakes O -time.Thusthetotalrun-timeofthealgorithm generatingtherainbowmatchingofsize in G is O n 2 Itisworthnotingthattheanalysisofthegreedyalgorithmusedintheproofof Theorem2.2couldbeimproved.Inparticular,thebound c i +1 c i )]TJ/F15 11.9552 Tf 11.874 0 Td [(2issharponly ifatstep i thereareanequalnumberofedgesofcolor i and i +1andbothendpoints of e i areincidenttoedgeswithcolor i +1.However,sinceoneoftheendpointsof e i hasdegreeatmost ,atmost )]TJ/F15 11.9552 Tf 12.115 0 Td [(1colorclassescanlosetwoedgesinstep i .Since themaximumsizeofacolorclassin G isatmost2 )]TJ/F15 11.9552 Tf 12.724 0 Td [(2,if G hasorderatleast 21

PAGE 32

6 ,thenthereareatleast3 = 2colorclasses.Thus,forsmallvaluesof i ,thebound c i 2 k )]TJ/F19 11.9552 Tf 12.407 0 Td [(i +1canlikelybeimproved.However,wedoubtthatsuchanalysisof thisalgorithmcanbeimprovedtoyieldaboundon j V G j betterthan6 22

PAGE 33

3. 2 -FactorswithaBoundedNumberofOddComponents 3.1Introduction Throughoutthischapterallcycleshaveanimplicitclockwiseorientation.For somevertex v onacycle C wewilldenotetherst,second,and i th predecessor respectivelysuccessorof v as v )]TJ/F15 11.9552 Tf 7.085 -4.339 Td [(, v \000 ,and v )]TJ/F20 7.9701 Tf 6.587 0 Td [(i respectively v + v ++ ,and v + i respectively.Given x and y on C C x;y isthesetofvertices f x + ;x ++ ;:::;y )]TJ/F22 11.9552 Tf 7.084 -4.339 Td [(g and C [ x;y ]istheset f x;x + ;:::;y g .Wealsolet xCy respectively xC )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(y denotethe path xx + :::y respectively xx )]TJ/F19 11.9552 Tf 9.077 -4.338 Td [(:::y .Givenasubgraph H of G ,foranedge e = xy wedene dist H e;v =min f dist H x;v ;dist H y;v g .Ifthereisnopathin H from anendpointof e to v ,thenwesaythat dist H e;v = 1 .Forsome U V G ,if U N v ,thenwesaythat v dominates U .Forasubgraph H of G andavertex v if v dominates V H ,thenwewillfrequentlyinsteadsaythat v dominates H .The circumference ofagraph G c G ,isthelengthofalongestcyclein G Recallthatwhenagraph G containsnocopiesoftheclaw, K 1 ; 3 G isclaw-free andthatwedenoteby h v ; x;y;z i theclawwithcentralvertex v andleaves x y ,and z .Likewise, h v ; x 1 ;x 2 ;:::;x t i denotesacopyof K 1 ;t .Forthesubgraphinducedby U V G weusethenotation G [ U ]. Agraphis hamiltonian ifitcontainsaspanningcycle,whichisa2-factorwith exactlyonecomponent.Theproblemofdeterminingwhenagraphishamiltonian isaclassicalandwidelystudiedproblemingraphtheorycf.[34,35].Asidefrom thehamiltonianproblem,therearemanyresultsthroughouttheliteraturethatgive conditionsensuringtheexistenceofa2-factorwithgivenproperties.Manyresultsof thistypeareoutlinedin[34,35],andtherehavebeennumerousdevelopmentssince thewritingofthosesurveyssee,forinstance,[2]. Let odd F denotethenumberofoddcyclesina2-factor F ofagraph G ,and let odd G denotetheminimumof odd F overall2-factors F of G .If G doesnot containa2-factor,wewillset odd G = 1 .Thefocusofthischapteristhefollowing. 23

PAGE 34

Problem3.1 Given k 0 ,determineconditionsthatguaranteeagraph G has odd G k Wenoteherethatdeterminingifagraphhastwodisjointperfectmatchings,or equivalentlyhas odd G =0isNP-complete,eveninthecasewhere G isabridgeless cubicgraph,whichiswhen G hasnocut-edgeandis3-regular.Thisfollowsfromthe fact[48]thatitisNP-hardtodetermineifacubicgraphhasaproperedge-coloring withthreecolors.Suchacoloringexistsifandonlyif G containsapairofdisjoint perfectmatchings. Inadditiontothegeneralliteratureonthestructureof2-factorsingraphs, odd G ariseswhenstudyingseveralotherinterestingproblems.Forinstance,resultsof HuckandKochol[51],HaggkvistandMcGuinness[40],andHuck[50]showedthat acubicbridgelessgraphwith odd G atmostfourhasafamily C ofatmostve evensubgraphssuchthateachedgeof G liesinexactlytwomembersof C .Asa consequence,suchgraphssatisfytheCircuitDoubleCoverCDCConjecturecf. [78,80].UnderstandingtheCDCforcubicgraphsiscrucialgiventhatSeymour[78] notedthatasmallestcounterexampletotheCDCConjecturemustbecubic. Notethat odd G isameasureofhowfar G isfromhavingapairofedge-disjoint perfectmatchings,as G containssuchapairifandonlyif odd G =0.Several otherrelatedmetricshavebeenconsidered.Let B 2 G = f B;B 0 : B;B 0 areedgedisjointmatchingsof G g P = f B;B 0 2 B 2 G : j E B j + j E B 0 j ismaximum g and H beamaximummatchingchosenfromthepairsofmatchingsin P .Then,given amaximummatching M in G G = j M j = j H j measureshowclose G istohaving apairofdisjointmatchingsofmaximumsize.Mkrtchyan,Musoyan,andTserunyan studied G andshowedthefollowing. Theorem3.2 [68] Foranygraph G G 5 4 .Thisboundistight. Anothermeasureofhowclose G istohavingapairofdisjointperfectmatchings 24

PAGE 35

isgivenbytheratioofedgescoveredbyapairofdisjointmatchingstothenumber ofverticesinagraph.ThisnotionwasexploredbyMkrtchyan,Petrosyan,and Vardanyan,andtheyshowedthefollowing. Theorem3.3 [69] Let G beacubicgraph.Then G containsapairofdisjointmatchingscoveringatleast 4 5 j V G j edgesin G Theproblemofdeterminingwhenagraphhas k edge-disjointperfectmatchings forsome k 2hasalsobeenstudiedinseveralcontexts.Hilton[46]andZhangand Zhu[91]examinedthenumberofdisjoint1-factorsinregulargraphs,andrecently Hou[49]consideredtheproblemfornearly-regulargraphsthosegraphswith G )]TJ/F19 11.9552 Tf -422.702 -23.981 Td [( G 1.HomanandRodger[47]givenecessaryandsucientconditionsfora completemultipartitegraphtocontain k edge-disjoint1-factors. Inthischapter,wearegenerallyinterestedininvestigatingProblem3.1inthe contextofforbiddensubgraphs.InSection3.2weexaminethestabilityof odd G undertheRyjacekclosureforclaw-freegraphs.InSection3.3wespecicallyconsider thecase k =0andexaminepairsofforbiddensubgraphsthatensureagraphhasa pairofdisjoint1-factors.Wethenpresentseveralconstructionsandopenproblems relatedtoProblem3.1inhighlyconnectedclaw-freegraphs. 3.2Closureand odd G forClaw-FreeGraphs In[73]Ryjacekintroducedthefollowingclosureconcept.Inagraph G ,avertex v is eligible if G [ N v ]isconnectedbutnotcomplete.Thegraphformedbycompleting theneighborhoodofavertex v isthe localcompletion of G at v .Theclosureofa graph G ,denoted cl G ,isconstructedbyiterativelyperformingthelocalcompletion operationateligibleverticesuntilnoneremain. ThisclosureisanimportanttoolforthestudyofcyclestructureandhamiltoniantypepropertiesinlargepartduetothefollowingresultfromRyjacek. Theorem3.4 [73] Let G beaclaw-freegraph.Then 25

PAGE 36

1.theclosure cl G iswell-dened, 2.thereisatriangle-freegraph H such cl G = L H ,where L H istheline graphof H 3. c G = c cl G Givenagraphclass C ,wesaythataproperty P is stable in C providedthatevery graph G in C hasproperty P ifandonlyif cl G hasproperty P .Thus,Theorem3.4 impliesthathamiltonicityandmoregenerallytheproperty c G = k "isstablein theclassofclaw-freegraphs. Ofparticularinteresthere,Ryjacek,Saito,andSchelpshowedthefollowing. Theorem3.5 [74] If G isaclaw-freegraph,then G hasa 2 -factorwithatmost k cyclesifandonlyif cl G hasa 2 -factorwithatmost k cycles. ThemainresultofthissectionisthefollowingextensionofTheorem3.5. Theorem3.6 [18] If G isaclaw-freegraph,then odd G k ifandonlyif odd cl G k: Proof: Clearly,if odd G k ,then odd cl G k ,soweproceedbydemonstratingtheconverse.Let G beaclaw-freegraphandlet G = G 0 ;G 1 ;:::;G t = cl G beasequenceofgraphssuchthat G i isthegraphformedbylocalcompletionof G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 atvertex v i .Supposetothecontrarythat odd G t k but odd G >k ,andlet i 1 betheminimumintegersuchthat G i hasa2-factor C withatmost k oddcyclesand denote v i as v Let E i C = E C E G i n E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,sothat E i C isthesetofedgesofthe2-factor C in G i whicharenotin G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,andobservethattheendpointsoftheseedgesareallin theneighborhoodof v .Choose C tominimize j E i C j andfurthermore,amongallsuch choicesof C selectanedge e 2 E i C suchthat dist C e;v ismaximum.Foreachcyclein 26

PAGE 37

C ,let C w denotethecyclecontainingaparticularvertex w andsimilarlylet C f denote thecyclecontainingaparticularedge f .Let e = u 1 u 2 ,where u 2 isthepredecessorof u 1 in C e ,andlet P beashortestpathbetween u 1 and u 2 in G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 [ N v ].Since G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 isclaw-free, P hasorderatmostfour;denotetheverticesof P as u 1 = x 1 x 2 :::x ` = u 2 with3 ` 4. Theproofproceedsincasesbyconsidering dist C e;v .Subcasesarethenbased onthelengthof P andthelocationofcertainverticesongivencyclesin C .Inmost cases,wedrawacontradictionbyndinga2-factorwithatmost k oddcyclesin G i thateitherusesfeweredgesin E i C than C ,orviolatesthepertinentassumptionabout dist C e;v .Webeginbyilluminatingseveralusefuledgesandnon-edgesof G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Claim3.7 If C v = C e ,thefollowinghold: 1. u 2 v )]TJ/F19 11.9552 Tf 11.796 -4.338 Td [(= 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 2. u 1 v + = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 3. v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 4.if u 2 6 = v + ,then u 2 v + 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 Proof: If u 2 v )]TJ/F15 11.9552 Tf 12.289 -4.339 Td [(isanedge,thenreplacing C v with u 2 v )]TJ/F19 11.9552 Tf 7.084 -4.339 Td [(C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v u 1 vC v u 2 resultsin a2-factor C 0 suchthat odd C 0 k and j E i C 0 j < j E i C j ,acontradiction.Similarly,if u 1 v + 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,replacing C v with u 1 v + C v u 2 vC )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v u 1 contradictstheminimalityof j E i C j Suppose C v isatriangle,then v )]TJ/F15 11.9552 Tf 11.217 -4.338 Td [(= u 1 and v + = u 2 ,soclearly, v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(v + isnotan edgeof G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .If C v isa4-cycle,then u 1 = v )]TJ/F15 11.9552 Tf 10.686 -4.338 Td [(or u 2 = v + .However,Partsand implythat u 2 v )]TJ/F19 11.9552 Tf 12.837 -4.338 Td [(= 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and u 1 v + = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,whichistosay v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Lastlyif C v hasmorethanfourverticesand v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thenreplacing C v with v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(v + C v u 2 vu 1 C v v )]TJ/F15 11.9552 Tf 10.987 -4.339 Td [(contradictstheminimalityof j E i C j 27

PAGE 38

Finally,consider h v ; u 1 ;u 2 ;v + i .Byassumption, u 1 u 2 = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,andsincePart holds u 1 v + = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thussince G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 isclaw-free, u 2 v + 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Thefollowingwillalsobeusefulthroughouttheremainderoftheproof. Claim3.8 Let f = w 1 w 2 2C suchthat C e 6 = C f .If u 1 w 1 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and u 2 w 2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,thenthereisacycle C suchthat V C = V C e [ V C f where e= 2 C Proof: Specicallyassumethat w 1 isthepredecessorof w 2 withoutlossof generalityon C f ,andreplace C e and C f with w 1 u 1 C u 1 u 2 w 2 C w 2 w 1 ,resultingina 2-factor C 0 suchthat j E i C 0 j < j E i C j Suppose C v 6 = C e ,andconsider v + ,thesuccessorof v on C v .Theclaw h v ; v + ;u 1 ;u 2 i in G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 impliesthatwithoutlossofgenerality v + u 2 isanedgein G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 since e = u 1 u 2 = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .However,byClaim3.8,wecanreplace C e and C v with u 2 v + C v vu 1 C e u 2 ,contradictingtheminimalityof j E i C j .Thus C v = C e ,sowemay applyClaim3.7asneededgoingforward. Wenowproceedbyconsidering dist C e;v Case1: dist C e;v 3. ByClaim3.7, u 2 v )]TJ/F19 11.9552 Tf 12.529 -4.338 Td [(= 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 u 1 v + = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,and u 2 v + 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .Consideringtheclaw h v ; u 1 ;u 2 ;v )]TJ/F22 11.9552 Tf 7.085 -4.339 Td [(i weseethat u 1 v )]TJ/F22 11.9552 Tf 11.895 -4.339 Td [(2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Wecannowreplace C v with C 1 v = u 1 C v v )]TJ/F19 11.9552 Tf 7.084 -4.339 Td [(u 1 and C 2 v = vC v u 2 v .If C v isodd,thisresultsina2-factor C 0 with j E i C 0 j < j E i C j .If C v iseven,then C 1 v and C 2 v havethesameparity.Ifbothare even,theminimalityof j E i C j iscontradicted.Otherwise,replace C v with u 1 C v vu 1 and v + C v u 2 v + ,tocontradicttheminimalityof j E i C j Case2: dist C e;v =2. Withoutlossofgenerality,assume e = v \000 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 = u 1 u 2 .Notethatsince dist C e;v =2,Claim3.7implies v + v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Wealsoclaimthatif x 2 6 = v )]TJ/F15 11.9552 Tf 7.085 -4.339 Td [(,then C x 2 6 = C v .Indeed,supposeotherwise andnotethatif x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v or x + 2 v isanedgeof G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,thenreplacing C v witheither 28

PAGE 39

x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 vv )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v \000 x 2 C v v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 v + C v x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 or x + 2 vv )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(v \000 x 2 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v + v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v x + 2 resultsina2-factor C 0 suchthat j E i C 0 j < j E i C j .Also,thisimpliesthat x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 6 = v + and x + 2 6 = v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 since v cannot beadjacentto x + 2 or x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 .Thus,since x 2 ; v;x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 ;x + 2 isnotinduced, x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 However,exchanging C v with vv )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v \000 x 2 v and v + C v x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 x + 2 C v v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 v + contradictsthe minimalityof j E i C j .Therefore x 2 = 2 V C v when x 2 6 = v )]TJ/F15 11.9552 Tf 7.084 -4.339 Td [(. Case2.1: ` =3, sothatinparticular P = v \000 x 2 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 = u 1 x 2 u 2 ByClaim3.7, u 2 = v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 isnotadjacentto v )]TJ/F15 11.9552 Tf 7.084 -4.339 Td [(,so x 2 6 = v )]TJ/F15 11.9552 Tf 7.085 -4.339 Td [(,whichimpliesthat C x 2 6 = C v Next, h x 2 ; x + 2 ;v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 ;v \000 i cannotbeinducedin G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,soconsidereachof x + 2 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 and x + 2 v \000 .If x + 2 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 or x + 2 v \000 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,thenreplacing C v and C x 2 witheither x + 2 C x 2 x 2 v \000 C v v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 x + 2 or x + 2 v \000 C v v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 x 2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x + 2 resultsina2-factor C 0 withatmost k oddcyclessuchthat j E i C 0 j < j E i C j .Thus,since h x 2 ; x + 2 ;v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 ;v \000 i is notinducedin G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 P containstwointernalvertices. Case2.2: C x 2 = C v AtthestartofCase2,weshowedthatif x 2 6 = v )]TJ/F15 11.9552 Tf 7.084 -4.339 Td [(,then C v 6 = C x 2 ,sowecan assume x 2 = v )]TJ/F15 11.9552 Tf 10.986 -4.339 Td [(and ` =4.ByClaim3.7, x 3 6 = v + ,since v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(v + = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 Wenowclaimthat x 3 isnoton C v .Indeed,assumeotherwiseandconsider h x 3 ; v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 ;v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 i .If v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,wemayreplace C v with v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v vv \000 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x 3 C v v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 resultingina2-factor C 0 with odd C 0 k suchthat j E i C 0 j < j E i C j .If v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,replacing C v with v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v + v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v x 3 vv \000 v )]TJ/F15 11.9552 Tf 12.87 -4.338 Td [(similarlycontradictsthe minimalityof j E i C j .However,fromClaim3.7, v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Thus x 3 isnoton C v ,so C x 3 6 = C v asclaimed. Considertheclaw x 3 ; x + 3 ;v )]TJ/F19 11.9552 Tf 7.084 -4.339 Td [(;v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 .Since v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 isnotanedge,oneof x + 3 v )]TJ/F15 11.9552 Tf -424.915 -28.319 Td [(or x + 3 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 isanedgein G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .If x + 3 v )]TJ/F22 11.9552 Tf 14.919 -4.338 Td [(2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,replace C v and C x 3 with vv \000 v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x + 3 C x 3 x 3 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v .Otherwise,if x + 3 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,replace C v and C x 3 with vv \000 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x 3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 3 x + 3 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v .Bothscenariosresultina2-factor C 0 withatmost k odd cyclessuchthat j E i C 0 j < j E i C j ,contradictingtheminimalityof j E i C j 29

PAGE 40

Case2.3: C x 3 = C v Inthiscase,werstshowthat x 3 6 = v + .Assumeotherwiseandconsider h x 2 ; v \000 ;v + ;x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 i .If v \000 x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thenreplacing C v and C x 2 with x 2 v + C v v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 v v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(v \000 x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x 2 contradictstheminimalityof j E i C j .If v + x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,thenbyreplacing C v and C x 2 with v + x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x 2 v \000 v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(vv )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v + in C wecontradicttheminimality of j E i C j .AsClaim3.7shows, v \000 v + = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,implyingthat h x 2 ; v \000 ;v + ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 i is induced,acontradiction,thus x 3 6 = v + Nowthat x 3 6 = v + ,weuse h v ; v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(;v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 ;x 2 i toshowthat v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x 2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Fromhere, h x 2 ; v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 ;x 3 i isusedtocompletethissubcase,as x 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 allowsustouse h x 3 ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 ;x + 3 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 i toshowthat x + 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 whichcanbe usedtocontradict j E i C j and x 3 v )]TJ/F15 11.9552 Tf 10.987 -4.338 Td [(allowsustocontradict x 2 = 2 C v ByClaim3.7, v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .If x 2 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,then v \000 x 2 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 contradictstheminimalityof P .Thus,since v ; v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(;v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 ;x 2 isnotinduced, x 2 v )]TJ/F22 11.9552 Tf 12.232 -4.338 Td [(2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Also,if v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 2 E i C ,thenreplacing C v and C x 2 with v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x 2 vC v v )]TJ/F15 11.9552 Tf -424.915 -28.319 Td [(resultsina2-factor C 0 with odd C 0 k suchthat dist C 0 e;v >dist C e;v ,acontradictiontothemaximalityof dist C e;v Since x 2 ; v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 ;x 3 isnotinduced,either x 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 or v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x 3 isanedgein G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 First,assumethat x 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .If x + 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 or x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 isanedgein G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,theneither x + 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 2 x 2 v \000 C v x 3 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v x + 3 or x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v + v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v x 3 vv )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(v \000 x 2 C x 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 canreplace C v and C x 2 ,resultingina2-factor C 0 withatmost k oddcyclessuchthat j E i C 0 j < j E i C j Since x 3 ; x + 3 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 isnotinduced, x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 x + 3 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .Butthenreplacing C v and C x 2 with x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x 2 v \000 C v x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(3 x + 3 C v v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 x 3 x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 contradictstheminimalityof j E i C j .This meansthat v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x 3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Sincewecouldhavechosen P = v \000 v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x 3 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 ,from Case2.2,theminimalityof j E i C j iscontradicted,completingCase2.3. Case2.4: C x 3 = C x 2 ByClaim3.8, x 3 = 2f x + 2 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 g .Suppose C x 2 isa4-cycle,andconsidertheclaw h x 2 ; x + 2 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 ;v \000 i .If x + 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,then v \000 C v v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 x 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 x 2 v \000 mayreplace C v 30

PAGE 41

and C x 2 ,resultingina2-factor C 0 withatmost k oddcyclessuchthat j E i C 0 j < j E i C j ,a contradiction.If x + 2 v \000 respectively x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v \000 isanedgein G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thenreplace C v and C x 2 with v \000 C v v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 x 3 C x 2 x + 2 v \000 respectively v \000 C v v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 x 3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 2 x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 v \000 tocontradict theminimalityof j E i C j .Thus,wecanassume C x 2 isnota4-cycle. Ifboth x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 and x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 x + 3 areedgesin G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thenreplacing C v and C x 2 with v \000 C v v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 x 3 x 2 v \000 and x + 2 C x 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 x + 3 C x 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 yieldsa2-factor C 0 with odd C 0 k and j E i C 0 j < j E i C j Firstassume x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Since x 2 ; x + 2 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 ;v isnotinduced,oneof x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v or x + 2 v isanedgeof G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Assumewithoutlossofgeneralitythat x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Considertheclaw v ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 ;v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;v + .ByClaim3.7, v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .If v + x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 thenreplacing C v and C x 2 with vv )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v v + x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x 2 v \000 v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(v resultsina2-factor C 0 with odd C 0 k suchthat j E i C 0 j < j E i C j .If v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thenreplace C v and C x 2 with vC v v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 v and x 2 C x 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(v \000 x 2 toagaincontradicttheminimalityof j E i C j However G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 isclaw-free,implyingthat x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,so x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 x + 3 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Since x + 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and x 3 ; x + 3 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 ;v isnotinduced,oneof x + 3 v or x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 v is anedgein G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Withoutlossofgenerality,assumethat x + 3 v 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Again,by Claim3.7 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .Thus,since v ; x + 3 ;v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;v + isnotinduced,either x + 3 v )]TJ/F22 11.9552 Tf 10.405 -4.338 Td [(2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 or x + 3 v + 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .If x + 3 v )]TJ/F22 11.9552 Tf 12.173 -4.338 Td [(2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,then v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x + 3 C x 2 x 3 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v vv \000 v )]TJ/F15 11.9552 Tf -424.916 -28.318 Td [(canreplace C v and C x 2 tocontradicttheminimalityof j E i C j .Otherwise,if x + 3 v + 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,replacing C v and C x 2 with x 2 v \000 v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(vx 2 and v + C v v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 x 3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 2 x + 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x + 3 v + contradictstheminimalityof j E i C j .ThiscontradictioncompletesCase2.4. Case2.5: C x 3 C x 2 and C v aredistinct Inthiscase,webeginbyusing h x 2 ; x 3 ;x + 2 ;v \000 i toshowthat x 3 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Thisedgeallowsustoconsider h x 3 ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 ;x + 2 ;v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 i .Sincethisclawisnotinducedin G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,weareabletouseedgesin G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 tocontradicttheminimalityof j E i C j Since x 2 ; x 3 ;x + 2 ;v \000 cannotbeinduced, x 3 v \000 x + 2 v \000 ,or x 3 x + 2 isanedge of G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Notethat x 3 v \000 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,asotherwise v \000 x 3 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 wouldcontradict 31

PAGE 42

theminimalityof P .Suppose x + 2 v \000 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,andconsider h v ; x 2 ;v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 i .If x 2 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,then v \000 x 2 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 contradictstheminimalityof P .ByClaim3.7 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Thismeans x 2 v )]TJ/F22 11.9552 Tf 10.879 -4.338 Td [(2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .However,nowreplace C v and C x 2 with v \000 x + 2 C x 2 x 2 v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(v \000 and vC v v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 v tocontradicttheminimalityof j E i C j .Therefore x 3 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Consider h x 3 ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 ;x + 2 ;v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 i .Thiscannotbeinduced,soatleastoneof x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 x + 2 x + 2 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 ,or x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 mustbeanedgeof G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .When x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,replace C v C x 2 ,and C x 3 with x + 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 3 x 3 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v \000 x 2 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 2 x + 2 ,resultingina2-factor C 0 suchthat j E i C 0 j < j E i C j .If x + 2 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,replace C v and C x 2 with x + 2 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v \000 x 2 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 2 x + 2 tocontradicttheminimalityof j E i C j .Finally,theedge x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(3 v )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 allowsustoreplace C v C x 2 ,and C x 3 with x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(3 v )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v v \000 x 2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x + 2 x 3 C x 3 x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(3 ,againcontradictingtheminimality of j E i C j .ThiscontradictioncompletestheproofofCase2.5,whichalsocompletesCase 2. Case3: dist C e;v =1. Withoutlossofgenerality,assume e = v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v \000 .ByClaim3.7, v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 so x 2 6 = v + Case3.1: C x 2 = C v If x 2 = v ++ ,thenreplacing C v with v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x 2 C v v \000 v + vv )]TJ/F15 11.9552 Tf 12.181 -4.338 Td [(resultsina2-factor C 0 withatmost k oddcyclessuchthat j E i C 0 j < j E i C j ,contradictingtheminimalityof j E i C j .Thus dist C v v;x 2 3. Nextweshowthateither h x 2 ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 ;v )]TJ/F22 11.9552 Tf 7.084 -4.339 Td [(i isinducedorthereisa2-factorin G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 whichcontradictstheminimalityof j E i C j .If x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thenreplacing C v with vx 2 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v x + 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v resultsina2-factor C 0 suchthat dist C 0 e;v >dist C e;v If x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v )]TJ/F15 11.9552 Tf 12.223 -4.338 Td [(or x + 2 v )]TJ/F15 11.9552 Tf 12.224 -4.338 Td [(isanedgeof G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 thenreplacing C v with vC v x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x 2 C v v \000 v or vC v x 2 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x + 2 C v v \000 v contradictstheminimalityof j E i C j .Thus x 2 ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 ;v )]TJ/F25 11.9552 Tf 7.085 5.346 Td [( isinduced,acontradiction.Therefore x 2 = 2 V C v Case3.2: ` =3, soinparticular P = v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x 2 v \000 = u 1 x 2 u 2 32

PAGE 43

ByClaim3.8, h x 2 ; x + 2 ;v \000 ;v )]TJ/F22 11.9552 Tf 7.085 -4.338 Td [(i isinducedin G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,so P musthavetwointernal vertices. Case3.3: C x 3 = C v Firstweshowthat x 3 6 = v + .Indeedassumeotherwise,andconsider x 2 ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 ;v + ;v )]TJ/F25 11.9552 Tf 7.085 5.345 Td [( .If v + x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thenwecanreplace C v and C x 2 with v + x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x 2 v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(vv \000 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v v + tocontradicttheminimalityof j E i C j .If v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 thenreplacing C v and C x 2 with v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 2 x 2 v + C v v \000 vv )]TJ/F15 11.9552 Tf 12.795 -4.338 Td [(contradictstheminimalityof j E i C j .By Claim3.7 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,so x 2 ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 ;v + ;v )]TJ/F25 11.9552 Tf 7.085 5.346 Td [( isinducedin G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 Wenowuse h x 2 ; v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;x 3 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 i toshowthat x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x 3 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .If x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v )]TJ/F22 11.9552 Tf 11.445 -4.338 Td [(2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 thenreplace C v and C x 2 with vx 2 C x 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v \000 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v tocontradictthemaximalityof dist C e;v .If x 3 v )]TJ/F22 11.9552 Tf 10.405 -4.338 Td [(2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,then v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x 3 v \000 contradictstheminimalityof P .Thus, x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 x 3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Finally,consider h x 3 ; x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(3 ;v \000 ;x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 i .If x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 v \000 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 replacing C v and C x 2 with x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(x 2 x 2 v )]TJ/F19 11.9552 Tf 7.084 -4.339 Td [(C v v \000 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 resultsina2-factor C 0 with odd C 0 k suchthat j E i C 0 j < j E i C j If x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 v \000 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,thenreplacing C v and C x 2 with v \000 C v )]TJ/F19 11.9552 Tf 7.085 -5.015 Td [(x 3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.859 -7.293 Td [(x 2 x 2 v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(C v x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 v \000 similarlycontradictstheminimalityof j E i C j .Finallyif x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,then vC v x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(x 2 x 2 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(C )]TJ/F20 7.9701 Tf -0.858 -7.294 Td [(v x 3 v canreplace C v and C x 2 tocontradictthemaximalityof dist C e;v .Since h x 3 ; x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(3 ;v \000 ;x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 i cannotbeinduced, x 3 = 2 C v Case3.4: C x 3 = C x 2 First,considering h x 2 ; x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 ;x + 2 ;v )]TJ/F22 11.9552 Tf 7.084 -4.338 Td [(i ,weshowthat x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .ByClaim3.8, x 3 6 = x )]TJ/F17 7.9701 Tf 0 -7.88 Td [(2 and x 3 6 = x + 2 .Withoutlossofgenerality, v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x + 2 = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 respectively v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 ,asotherwise,replacing C v and C x 2 with v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x + 2 C x 2 x 2 vC v v )]TJ/F15 11.9552 Tf 10.366 -4.339 Td [(resultsina2-factor suchthat C v = C x 2 ,whichwasconsideredinCase3.1,andso x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Nowconsidertheclaw h x 3 ; x + 3 ;x 2 ;v \000 i .Bytheminimalityof P x 2 v \000 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .If v \000 x + 3 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,thenreplacing C v and C x 2 with v \000 x + 3 C x 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 C x 2 x 3 x 2 v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(C v v \000 resultsina2-factor C 0 withatmost k oddcyclessuchthat j E i C 0 j < j E i C j Otherwise,if x 2 x + 3 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,thenreplace C v and C x 2 with x 2 x + 3 C x 2 x )]TJ/F17 7.9701 Tf 0 -7.879 Td [(2 x + 2 C x 2 x 3 v \000 33

PAGE 44

C )]TJ/F20 7.9701 Tf -0.859 -7.294 Td [(v v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x 2 tocontradicttheminimalityof j E i C j .Thiscontradictioncompletestheproof ofCase3.4. Case3.5: C x 3 C x 2 and C v aredistinct First,considertheclaw h x 2 ; x + 2 ;v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(;x 3 i .AsinCase3.4, v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x + 2 = 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 as otherwise,replacing C v and C x 2 with v )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x + 2 C x 2 x 2 vC v v )]TJ/F15 11.9552 Tf 10.48 -4.339 Td [(resultsina2-factorsuchthat C v = C x 2 ,consideredinCase3.1.Bytheminimalityof P v )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x 3 = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .Sowe havethat x 3 x + 2 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 Next,weuse h x 3 ; x 2 ;x + 3 ;v \000 i toshowthat x + 3 v \000 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Bytheminimalityof P x 2 v \000 = 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .If x + 3 x 2 2 E G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,replacing C x 2 and C x 3 with x 2 x + 3 C x 3 x 3 x + 2 C x 2 x 2 yieldsa2-factorsuchthat C x 2 = C x 3 ,whichisCase3.4. Thus, x + 3 v \000 2 E G i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ;however,wecannowreplace C v C x 2 ,and C x 3 with v \000 x + 3 C x 3 x 3 x + 2 C x 2 x 2 v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(C v v \000 ,resultingina2-factor C 0 suchthat j E i C 0 j < j E i C j .This contradictioncompletestheproofofCase3.5,andtheproofofTheorem3.6. 3.3Disjoint1-factors Asnotedintheintroduction,a2-factorwithnooddcomponentsisequivalentto apairofdisjoint1-factors.Goingforwardwewillrefertosucha2-factorasan even 2 -factor .ThissectionspecicallyconsidersProblem3.1when k =0. Problem3.9 Determineconditionsinagraph G whichguaranteethat G hasapair ofdisjointperfectmatchings. Inlightofthisproblem,wehavethefollowingimmediatecorollaryofTheorem3.6 inthecase k =0. Corollary3.10 [18] Let G beaclaw-freegraph.Then G containsapairofdisjoint perfectmatchingsifandonlyif cl G containsapairofdisjointperfectmatchings. 3.3.1ForbiddenSubgraphConditions 34

PAGE 45

Itisclearthatifagraph G hasaneven2-factor,then G hasa2-factor,sowewill considerconditionsthatensureagraphhasa2-factor.In[31]Faudree,Faudree,and Ryjacekcharacterizedthepairsofforbiddensubgraphswhichguaranteethatalarge enough2-connectedgraphhasa2-factor.Intheresultsthatfollow,the generalized net N i;j;k isthegraphobtainedbyassociatingoneendpointofeachofthepaths P i +1 ;P j +1 and P k +1 withdistinctverticesofatriangle.Followingconvention,wewill let B i;j and Z i denotethegeneralizednets N i;j; 0and N i; 0 ; 0,respectively. Theorem3.11 [31] Let X and Y beconnectedgraphswithatleastthreeedges,and let G bea 2 -connectedgraphoforder n 10 .Then, G being f X;Y g -freeimpliesthat G hasa 2 -factorifandonlyif,uptotheorderofthepairs, X = K 1 ; 3 and Y isa subgraphofeither P 7 Z 4 B ; 1 ,or N ; 1 ; 1 ,or X = K 1 ; 4 and Y = P 4 Webeginbyconsidering f K 1 ; 4 ;P 4 g -freegraphs.Let E bethefamilyofgraphs composedoftwooddcliquesandanedge wz joinedtotwovertices x and y where x mayormaynotbeadjacentto y seeFigure3.1.Everygraph G in E is f K 1 ; 4 ;P 4 g freeanddoesnotcontainapairofdisjoint1-factors,astheedge wz isineveryperfect matchingof G .Ournextresultdemonstratesthatgraphsinthefamily E aretheonly 2-connected f K 1 ; 4 ;P 4 g -freegraphswithnoeven2-factor.Werequirethefollowing lemmafromFaudree,Faudree,andRyjacek. Lemma3.12 [31] If G isa 2 -connected f K 1 ; 4 ;P 4 g -freegraphoforderatleastnine, then G hasa 2 -factorwithatmosttwocomponents. Theorem3.13 [18] Any 2 -connected f K 1 ; 4 ;P 4 g -freegraphofevenorderatleastten containsaneven 2 -factororisamemberofthefamily E Proof: Let G bea2-connected f K 1 ; 4 ;P 4 g -freegraphofevenorder n 10that doesnotcontainaneven2-factor.Thusevery2-factorhasatleasttwocomponents andbyLemma3.12thereisa2-factor F withexactlytwocomponents,callthem 35

PAGE 46

Figure3.1: Thefamily E of2-connected f K 1 ; 4 ;P 4 g -freegraphsthatdonotcontain disjoint1-factors. C 1 and C 2 .Since G is2-connectedthereareatleasttwodisjointedges, e 1 and e 2 between C 1 and C 2 .Let e 1 = xx 0 and e 2 = yy 0 ,where x;y 2 C 1 and x 0 ;y 0 2 C 2 If xy 2 E C 1 and x 0 y 0 2 E C 2 ,then C 1 and C 2 canbecombinedintoasingle cycle xC 1 yy 0 C 2 )]TJ/F19 11.9552 Tf 7.084 -4.339 Td [(x 0 x .Since G is P 4 -free, G [ f x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(;x;x 0 ;x 0 + g ]isnotaninduced P 4 .If x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x 0 + isanedge,then xC 1 x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x 0 + C 2 x 0 x isaneven2-factorin G ,sowithoutlossof generality, xx 0 + 2 E G .Similarly,since G [ f x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(;x;x 0 + ;x 0 ++ g ]isnotaninduced P 4 xx 0 ++ 2 E G .Asimilarargumentshowsthatthereisaninduced P 4 foreachedge from x to C 2 unless x dominates C 2 .Now,if xy 2 E C 1 ,thenreplace C 1 and C 2 with yC 1 xy 0 + C 2 y 0 y ,so y )]TJ/F22 11.9552 Tf 11.604 -4.338 Td [(6 = x .Forthesamereasonthat x dominates C 2 y must alsodominate C 2 .Notethatif y 0 dominated C 1 instead,thenwecouldcombine C 1 and C 2 Let D bethesetofverticesin C 1 thatdominate C 2 .Therecanbenotwoedges f 1 = uv 2 E C 1 and f 2 = u 0 v 0 2 E C 2 suchthat uu 0 2 E G and vv 0 2 E G lest C 1 and C 2 becombined,andthereareatleasttwoverticesin D ,so j V C 1 j 4 whichimpliesthat j V C 1 j 5since j V C 1 j isodd.Ifforsomevertex v 2 D ,the edge v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + isin G ,then C 1 canbeshortenedbyusingtheedge v )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(v + toskip v ,and C 2 canbeextendedbyincluding v ,forminganeven2-factor.Thusnosuchedge exists.Sinceforanypairofvertices v 1 and v 2 in C 2 ,thegraph h x ; x )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;x + ;v 1 ;v 2 i is notinduced,theedge v 1 v 2 exists.Thus V C 2 formsaclique. Suppose e 1 and e 2 werechosensuchthat C 1 x;y D = ; .Let v beanyver36

PAGE 47

texin C 1 x;y )]TJ/F15 11.9552 Tf 7.085 -4.338 Td [(suchthat xv isanedgeof G .Thentheedge xv + isin G since G [ f x 0 ;x;v;v + g ]isnotaninduced P 4 .Now x dominates C 1 x;y andsimilarly y dominates C 1 x;y .Let i bethesmallestintegersuchthat x + i 2 C 1 x;y doesnot dominate C 1 x;y ,andlet j bethesmallestintegersuchthat y )]TJ/F20 7.9701 Tf 6.586 0 Td [(j isnotadjacent to x + i .Consider x ; x 0 ;x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(;x + i ;y )]TJ/F20 7.9701 Tf 6.586 0 Td [(j .Ifeither x )]TJ/F19 11.9552 Tf 7.084 -4.339 Td [(x + i or x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(y )]TJ/F20 7.9701 Tf 6.586 0 Td [(j isanedge,then x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x + i C 1 y )]TJ/F19 11.9552 Tf 7.084 -4.339 Td [(x + i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 C 1 )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(xx 0 C 2 x 0)]TJ/F19 11.9552 Tf 9.382 -4.339 Td [(yC 1 x )]TJ/F15 11.9552 Tf 9.686 -4.339 Td [(or x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(y )]TJ/F20 7.9701 Tf 6.587 0 Td [(j C 1 y )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(x + i C 1 y )]TJ/F20 7.9701 Tf 6.586 0 Td [(j )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 x + i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 C 1 )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(xx 0 C 2 x 0)]TJ/F19 11.9552 Tf 9.382 -4.338 Td [(yC 1 x )]TJ/F15 11.9552 Tf 10.29 -4.338 Td [(isahamiltoniancycle.If x 0 x )]TJ/F22 11.9552 Tf 10.405 -4.338 Td [(2 E G x 0 x )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(C 1 )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(xx 0 + C 2 )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x isahamiltonian cycle,andsimilarlyif x 0 x + i 2 E G or x 0 y )]TJ/F20 7.9701 Tf 6.586 0 Td [(j 2 E G ,then x 0 x + i C 1 )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x + x + i +1 C 1 )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(xx 0 + C 2 )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(x 0 or x 0 y )]TJ/F20 7.9701 Tf 6.587 0 Td [(j C 1 )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x + y )]TJ/F20 7.9701 Tf 6.586 0 Td [(j +1 C 1 )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(xx 0 + C 2 )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x 0 isahamiltoniancycle.Consequently,no such i existsand G [ C 1 x;y ]formsaclique.If j D j =2,thenthisargumentcanbe repeatedtoshowthat G [ C 1 y;x ]isalsoaclique. Suppose j D j 3andlet z 2 D suchthat C 1 x;z D = f y g .Asinthecasethat j D j =2, G [ C 1 y;z ]formsaclique. Ifthereisanedgebetween C 1 x;y and C 1 y;z ,thenwemayrearrange C 1 suchthat y )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(y + isanedgeandremove y from C 1 andadditto C 2 ,andtherefore nosuchedgeexists.If x )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(y + 2 E G ,then C 1 [ x;y ]canbepulledinto C 2 toform b C 1 = y + C 1 x )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(y + and b C 2 = xC 1 yx 0)]TJ/F19 11.9552 Tf 9.381 -4.338 Td [(C 2 )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x 0 x .Considerthepath G [ f x \000 ;x )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;x;x + g ]. Frombefore, x )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(x + isnotanedge,and x \000 x + allowsustoreplace b C 1 and b C 2 with x \000 x + b C 2 )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(xx )]TJ/F25 11.9552 Tf 9.356 -1.316 Td [(b C 1 x \000 ,so xx \000 mustbeanedge.Iteratingthisargument,weget that x dominates b C 1 .However,since z dominates C 2 zx 0 2 E G andthecycle zx 0 b C 2 xz + b C 1 z spans G andsoisaneven2-factor.Thus,if x )]TJ/F19 11.9552 Tf 7.085 -4.339 Td [(y + 2 E G ,then j D j =2. Nowif xy 2 E G ,then G [ f x )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;x;y;y + g ]isaninduced P 4 ,otherwiseconsider G [ f x;y )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;y;y + g ].If xy + 2 E G ,then h x ; x )]TJ/F19 11.9552 Tf 7.084 -4.338 Td [(;x + ;y + ;x 0 i isinduced.Thus, G [ f x;y )]TJ/F19 11.9552 Tf 7.085 -4.338 Td [(;y;y + g ]isaninduced P 4 unless j D j =2. Asshownabove, j C 1 x;y j > 0.Since C 1 isanoddcycle,either j C 1 x;y j or j C 1 y;x j iseven,sowithoutlossofgenerality,assumethat j C 1 x;y j iseven. 37

PAGE 48

If j C 1 x;y j 4,then C 1 [ y;x C 1 x;y ,and C 2 + x formaneven2-factor.If j C 1 x;y j =2,then G isamemberof E Turningourattentiontoconnected,butnotnecessarily2-connected,graphs, FujisawaandSaitoshowedthefollowing. Theorem3.14 [33] Let F 1 and F 2 beconnectedgraphsoforderatleastthree.Then thereexistsapositiveinteger n 0 suchthateveryconnected f F 1 ;F 2 g -freegraphoforder atleast n 0 andminimumdegreeatleasttwohasa 2 -factorifandonlyifwithoutloss ofgenerality F 1 isasubgraphof K 1 ; 3 and F 2 isasubgraphof Z 2 Wegivethefollowingrelatedresultfordisjoint1-factors. Theorem3.15 [18] Everyconnected f K 1 ; 3 ;Z 2 g -freegraphofevenorderwithminimumdegree G = 3 containsaneven 2 -factorwithatmosttwocomponents. Proof: Let G beaconnected f K 1 ; 3 ;Z 2 g -freegraphofevenorder.Gouldand Jacobson[36]showedthatevery2-connected f K 1 ; 3 ;Z 2 g -freegraphishamiltonian,so weneedonlyconsiderthecasewhere G hasacutvertex x .Since G is K 1 ; 3 -free, x mustlieinexactlytwoblocks,solet B 1 and B 2 betheblockscontaining x Since G isclaw-free,theneighborhoodofanyvertexisconnectedortwodisjoint cliques,so G [ N B 1 x ]and G [ N B 2 x ]arecliques.Further,since d x 3,without lossofgenerality, j N B 1 x j 2.Let v 1 ;v 2 2 N B 1 x and u 2 N B 2 x .Supposethat N B 2 x 6 = V B 2 ,andlet w 2 V B 2 n N x suchthat uw 2 E G .Weknowthat thereissucha w since G isconnected.However, G [ f x;v 1 ;v 2 ;u;w g ]isaninduced Z 2 Thus N B 2 x = V B 2 ,andsimilarly N B 1 x = V B 1 Finally,supposethereissomethirdblock, B 3 ,whichnecessarilycannotcontain x .Withoutlossofgenerality,let v 2 B 2 B 3 beacutvertexof G .Let u 2 N B 3 v and x betheonlycutvertexof B 1 .Thismeansthatsince G 3, j V B 1 j 4 and x isadjacentto v .Now,let x 1 ;x 2 2 V B 1 suchthat x 1 6 = x and x 2 6 = x .Then G [ f x 1 ;x 2 ;x;v;u g ]isaninduced Z 2 ,acontradiction. 38

PAGE 49

Thus G consistsofblocks B 1 and B 2 ,bothofwhicharecomplete.Since G hasevenorder,oneblockhasevenorderandtheotheroddorder.Withoutloss ofgenerality,let B 1 haveoddorder.Then B 1 )-272(f x g and B 2 areeven2-connected f K 1 ; 3 ;Z 2 g -freegraphssoarehamiltonian,andthisyieldsaneven2-factorof G Consideringeitheracliqueofanysizewithapendantedgeorthegraphobtained byidentifyingavertexinacliqueofanysizeandavertexof K 3 ,theminimumdegree conditioninTheorem3.15cannotbeweakenedinordertostillguaranteeaneven 2-factorinthegraph. 3.3.2MinimumDegreeandConnectivityConditions Thereareanumberofresultsthatgiveminimumdegreeandconnectivityconditionsimplyingaclaw-freegraphhasa2-factor.EgawaandOta[27]andChoudum andPaulraj[13]independentlyshowedthataclaw-freegraphwithminimumdegree atleastfourhasa2-factor.Subsequently,Yoshimoto[90]andAldred,Egawa,Fujisawa,OtaandSaito[3]demonstratedthat G 3suceswhen G is2-connected andclaw-free. Weshownextthattherearenosuchconditionsthatensurea3-connectedclawfreegraphofevenordercontainsaneven2-factor.Let P bethePetersengraph,and dene P asthegraphobtainedbyreplacingeachvertexof P withacliqueoforder +1.Thethreeincidentedgesatonevertex v of P arenowincidentwiththree dierentverticesinthecliquereplacing v in P .SeeFigure3.2for P 4 Theorem3.16 [18] Foreven 4 P isa 3 -connected K 1 ; 3 -freegraphwithminimumdegree andnoeven 2 -factor. Proof: Itisclearthat P is3-connectedsince P is3-connected.Theneighborhoodofanyvertexiseitheracliqueortwodisjointcliques,thus P is K 1 ; 3 -free. Consideraperfectmatching M in P ,andaperfectmatching M 0 thatisdisjoint from M .Let F P E P bethesetofedgesthatwereoriginallyedgesof P these aretheedgesthatarenotcompletelycontainedinasinglecliqueoforder +1.Each 39

PAGE 50

Figure3.2: Thegraph P 4 cliqueisodd,so M mustcontain B F P whereeachcliquecontainsoneorthree verticesof V B .If V B hasthreeverticesinasingleclique C ,thenthereisno M 0 since P )]TJ/F19 11.9552 Tf 9.544 0 Td [(M has C asanoddcomponent.Therefore, V B containsexactlyonevertex ineachclique,andcorrespondstoaperfectmatchingin P .However,anyperfect matchingin P leavestwocomponents,eachisomorphicto C 5 .Thecorresponding componentsin P arecopiesof C 5 withverticesreplacedbyoddcliques.Thesetwo componentsareoddoforderatleast5 +1,andso M 0 cannotexist.Thus, P doesnotcontainaneven2-factor. 40

PAGE 51

4.ExtremalTheoremsforDegreeSequencePacking 4.1Introduction Thereareanumberofnecessaryandsucientconditionsforasequencetobe graphic,includingtheseminalHavel-HakimiAlgorithm[42,45]andtheErd}os-Gallai Criteria[28].However,agivengraphicsequencemayhavealargefamilyofnonisomorphicrealizations,andassuchconsiderableattentionhasbeengiventothestudy ofwhenagraphicsequencehasarealizationwithagivenproperty.Suchproblems canbedividedintotwobroadclasses,describedasforcible"problemsandpotential"problemsin[70].Givenagraphproperty P ,wesaythatagraphicsequence is forcibly P -graphic ifeveryrealizationof hasproperty P ,andthat is potentially P -graphic ifatleastonerealizationof hasproperty P Resultsonforcibledegreesequencesareoftenstatedastraditionalproblemsin structuralorextremalgraphtheory,whereanecessaryand/orsucientconditionis givenintermsofthedegreesoftheverticesorequivalentlythenumberofedgesof agivengraph.Forinstance,minimumdegreethresholdsfortheexistenceofcertain graphstructures,suchasthethresholdforhamiltonicityinDirac'sTheorem[23],can bethoughtofasforcibletheorems.Twoolder,butexceptionallythoroughsurveys onforcibleandpotentialproblemsareduetoHakimiandSchmeichel[43]andRao [71]andamorerecentsurveyonforcibleChvatal-Type"theoremsinthespiritof [15]isduetoBaueretal.[5]. Anumberofdegreesequenceanaloguestoclassicalproblemsinextremalgraph theoryappearthroughouttheliterature,includingpotentiallygraphicsequencevariantsofHadwiger'sConjecture[26,72],theErd}os-SosConjecture[63],graphRamsey numbers[10]andtheTuranproblemc.f.[32].Inthischapter,weconsideranextensionoftheclassicalgraphpackingliteraturetodegreesequences.Inparticular,we proveapotentially P -graphicanaloguetoawidely-studiedgraphpackingconjecture ofBollobasandEldridge[7]and,independently,Catlin[12],whichimpliesagraphic 41

PAGE 52

sequenceversionoftheSauer-Spencergraphpackingtheorem[76].Weconcludeby usingsimilartechniquestoproveapairofrelatedresultsthathaveapplicationsto discreteimagingscience. 4.1.1GraphPacking Two n -vertexgraphs G 1 and G 2 pack if G 1 isasubgraphof G 2 ,oralternatively if G 1 and G 2 canbeexpressedasedge-disjointsubgraphsof K n .Graphpacking hasreceivedagreatdealofattentionwithinterestingresultsandchallengingopen problemsappearingthroughouttheliterature[56],[88]and[89]aredetailedand usefulsurveys. In1978,SauerandSpencerprovedthefollowingclassicaltheorem. Theorem4.1 [76] Let G 1 and G 2 begraphsoforder n withmaximumdegrees 1 and 2 respectively.If 1 2 < n 2 ; then G 1 and G 2 pack. LikelythemostnotableopenconjectureingraphpackingisduetoBollobasand Eldridge[7]and,independently,Catlin[12]. Conjecture4.2 [7,12] Let G 1 and G 2 be n -vertexgraphswithmaximumdegrees 1 and 2 ,respectively.If 1 +1 2 +1 n +1 then G 1 and G 2 pack. Wenotethat,iftrue,Conjecture4.2impliesTheorem4.1.TheBollobas-EldridgeCatlinconjecturehasbeensettledinseveralcases,includingwhen 1 2byAigner andBrandt[1]andAlonandFisher[4].Thecasewhen 1 =3wasshownbyCsaba, Shokoufandeh,andSzemeredi[17]forlarge n utilizingtheregularitylemma.For 1 ; 2 300,Kaul,KostochkaandYu[55]showedthat 1 +1 2 +1 0 : 6 n +1 42

PAGE 53

impliesthatthetwographspack,whichimprovestheSauer-Spencertheorem,andis apartialsolutiontoConjecture4.2.OtherpartialresultswereobtainedbyCorradi andHajnal[16]andHajnalandSzemeredi[41]. 4.1.2PackingGraphicSequences Thenotionofpackinggraphicsequenceswasinvestigatedin[11],wherethefollowingkeydenitionappears.If 1 and 2 arenotnecessarilymonotonegraphic sequences,with 1 = d 1 ;:::;d n and 2 = d 1 ;:::;d n ,then 1 and 2 pack if thereexistedge-disjointgraphs G 1 and G 2 ,bothwithvertexset f v 1 ;:::;v n g ,such that d G 1 v i = d i and d G 2 v i = d i : Itiscriticaltonoteherethattheorderofthetermsin 1 and 2 isxed,so thatthestatement 1 and 2 pack"isnotequivalentto 1 and 2 haverealizations thatpack".Thisframeworkallowsforsomeinterestingdistinctionsbetweenpacking graphsandpackinggraphicsequences.Ontheotherhand,whenatheoremcerties thatapairofgraphspack,itgenerallydoesnotgiveinsightinto how theypack. Here,byxingtheorderingof 1 and 2 ,weprovideinsightintohowapairofgraphs withthesedegreesequencesmightfeasiblypack,ifinfacttheydo. Givenanotnecessarilygraphicsequence ,let and denotethemaximumandminimumtermsin ,respectively.Further,giventwosequences 1 and 2 ofthesamelength,let 1 + 2 denotethevectorsum"of 1 and 2 .Oneofthe mainresultsfrom[11]isthefollowing. Theorem4.3 Let 1 and 2 be n -termgraphicsequenceswith = 1 + 2 and = 1 + 2 .If p 2 n )]TJ/F15 11.9552 Tf 11.956 0 Td [( )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 ; then 1 and 2 pack,exceptthatstrictinequalityisrequiredwhen =1 .Thisresult issharpforall n and 43

PAGE 54

Aswasnotedin[11],thistheoremcanbeviewedasanadditive"analoguetothe Sauer-Spencertheorem,since 1 + 2 < p 2 n impliesthat 1 2 < n 2 .Wemodify andstrengthenthetechniquesintroducedintheproofofTheorem4.3toobtainour mainresultshere. 4.1.3StatementofMainResults Throughoutthestatementandproofofthefollowingresults,givengraphicsequences 1 and 2 welet i = i and i = i for i 2f 1 ; 2 g .Themainresult ofthischapterisasfollows. Theorem4.4 [19] Let 1 and 2 begraphicsequenceswith 2 1 and 1 1 .If 8 > > < > > : 2 +1 1 + 1 1 n +1 when 2 +2 1 + 1 2 +1+ 1 + 1 2 4 1 n +1 when 2 +2 < 1 + 1 ; then 1 and 2 pack. Theorem4.4holdsregardlessoftheorderingsof 1 and 2 althoughtheseorderingsarexed.Giventhis,wecannotassumethat 1 = 2 =0,asitwouldbe possibletoorder 1 and 2 sothatthezerotermscorrespond,whichwouldimpactthe relativestrengthofthehypothesis.Itseemsfeasiblethattheconditionsthat 1 2 and 1 1couldbereplacedbytheweakerhypothesisthat 1 + 2 1,althoughweareunabletoobtainsucharesultatthistime. Asimplecalculation,whichwegivebelow,demonstratesthatTheorem4.4implies thefollowingdirectanaloguetotheBollobas-Eldridge-Catlinconjecture. Corollary4.5 [19] Let 1 and 2 begraphicsequenceswith 2 1 and 1 1 .If 1 +1 2 +1 n +1 ,then 1 and 2 pack.Thisresultisbestpossible. MuchastheBollobas-Eldridge-CatlinconjectureimpliestheSauer-Spencertheorem,wealsoobtainthefollowing. 44

PAGE 55

Corollary4.6 [19] Let 1 and 2 begraphicsequenceswith 2 1 and 1 1 .If 1 2 < n 2 ,then 1 and 2 pack.Thisresultisbestpossible. 4.2Sharpness In[54],KaulandKostochkacharacterizedthesharpnessexamplesforTheorem 4.1.Specically,graphs G 1 and G 2 satisfying 1 2 = n 2 pack,unless n iseven, G 1 isamatchingofsize n 2 ,and G 2 iseither K n 2 ; n 2 oranygraphthatcontains K n 2 +1 asa component. Inasimilarmanner,toseethatCorollaries4.5and4.6aresharp,let n beeven andconsider 1 = n and 2 = n 2 n +2 2 ; 0 n )]TJ/F18 5.9776 Tf 5.756 0 Td [(2 2 .Thesesequencesareuniquelyrealized asaperfectmatchingand K n 2 +1 [ )]TJ/F20 7.9701 Tf 6.675 -4.976 Td [(n 2 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 K 1 ,whichdonotpack,regardlessofthe orderingsof 1 and 2 .Weshowthefollowing. Theorem4.7 [19] Theorem4.4isstrictlystrongerthanCorollary4.5unless 1 =1 Further,Corollary4.5isstrictlystrongerthanCorollary4.6unless 1 = 1 =1 Proof: Werstnotethatwhen 1 =1,theconditionsforTheorem4.4and Corollary4.5areequivalent,sowesupposethat 1 > 1. If 2 +2 1 + 1 ,thensince 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 > 0and 1 > 1,wehave 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 < 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 1 2 + 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 1 : Thisyields 1 2 + 1 2 + 1 + 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 < 1 1 2 + 1 2 + 1 1 ; or 2 +1 1 + 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 1 < 2 +1 1 +1 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 n: If 2 +2 < 1 + 1 thenwehavethat 1 2 +3 )]TJ/F15 11.9552 Tf 12.014 0 Td [( 1 .Also, 1 1 implies 45

PAGE 56

1 + 1 2 1 .Usingthesetwoinequalities,wehavethefollowing 2 +1+ 1 + 1 2 4 1 )]TJ/F15 11.9552 Tf 15.182 8.088 Td [(1 1 2 +1+2 1 2 4 2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 )]TJ/F15 11.9552 Tf 42.153 8.088 Td [(1 2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 : Itsucestoshowthat 2 +1+2 1 2 4 2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 )]TJ/F15 11.9552 Tf 42.153 8.087 Td [(1 2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 < 1 2 + 1 + 2 +1 : .1 Inequality.1simpliesto 4 2 1 2 +8 2 1 < 4 1 2 2 +3 2 2 +14 2 +8 1 2 +4 1 +15 ; whichisalwaystrue. Notethatif 1 =1,thentheconditionsforCorollary4.5andCorollary4.6 arethesame.Wenowshowthatif 1 > 1,thenCorollary4.5isstrictlystronger thanCorollary4.6.TheconditioninCorollary4.5is 1 2 + 1 + 2 n andthe conditioninCorollary4.6is2 1 2 +1 n .Since 1 2 + 1 + 2 < 2 1 2 +1 when 1 > 1,theassertionholds. Kundu's k -factorTheorem[60],provedindependentlybyLovaszfor k =1[66], statesthatagraphicsequence = d 1 ;:::;d n hasarealizationcontaininga k -factor ifandonlyif 0 = d 1 )]TJ/F19 11.9552 Tf 12.169 0 Td [(k;:::;d n )]TJ/F19 11.9552 Tf 12.169 0 Td [(k isalsographic.ThistogetherwithTheorem 4.7allowsustopartiallycharacterizethesharpnessofCorollary4.5andcompletely characterizethesharpnessofCorollary4.6.Thelattercharacterizationisanalogous tothecharacterizationforgraphpackingfrom[54]. Theorem4.8 [19] Let 1 and 2 begraphicsequenceswith 2 1 and 1 1 aIf 1 +1 2 +1 n +2 and 1 6 =1 ; 46

PAGE 57

then 1 and 2 pack. bIf 1 2 = n 2 ; then 1 and 2 packunless 1 =1 and 1 + 2 isnotgraphic. 4.3ProofsofTheorem4.4,Corollary4.5,andCorollary4.6 Let G 1 = V;E 1 and G 2 = V;E 2 begraphs.Wesayavertexpair x;y isa badpairfor G 1 ;G 2 ora G 1 ;G 2 -badpair if xy 2 E 1 E 2 .Let b G 1 ;G 2 denotethe numberof G 1 ;G 2 -badpairs.WebeginbyprovingTheorem4.4. Proof:ofTheorem4.4 Let 1 and 2 begraphicsequencesthatdonot pack.Choose G 1 = G 1 and G 2 = G 2 tohavethefewestbadpairsamong allrealizationsof 1 and 2 andlet G = G 1 [ G 2 .Foragiven G 1 ;G 2 -badpair x;y wedene I x;y = V )]TJ/F15 11.9552 Tf 12.627 0 Td [( N G x [ N G y .Amongallchoicesof G 1 and G 2 thatminimize b G 1 ;G 2 ,choose G 1 G 2 andabadpair x;y suchthatthesizeof I = I x;y ismaximum.For i 2f 1 ; 2 g ,let Q i y be N G i y )]TJ/F19 11.9552 Tf 11.062 0 Td [(N G [ x ]anddene Q i x similarly.Ifeither Q 1 x or Q 1 y isnonempty,assumewithoutlossofgenerality that j Q 1 x jj Q 1 y j .Otherwise,ifboth Q 1 x and Q 1 y areempty,thenassume withoutlossofgeneralitythat j Q 2 x jj Q 2 y j Throughouttheproofwewillmakeuseofthefollowingsets.First,let Y = V G )]TJ/F19 11.9552 Tf 12.318 0 Td [(N G [ y ].Dene A tobeasubsetof N G 1 Y suchthateveryvertexof A has atleasttwoneighborsin G 1 in Y .Finally,let B = N G 1 Y )]TJ/F19 11.9552 Tf 12.191 0 Td [(A and R = A [f v 2 N G [ y ]: A N G v g WeproveTheorem4.4bycountingthenumberofedgesin G 1 between R and V G )]TJ/F19 11.9552 Tf 11.876 0 Td [(R toreachacontradiction.Inordertogainthedesiredcount,werstshow particularedgestructuresin I Y ,and N G 1 Y .Wethenshowthat A isnotempty andfurtherthat R isavertexcoverof G 1 47

PAGE 58

Asitwillbeusefulinvariousinstances,wenextshowthatifthecondition 2 +1 1 + 1 1 n +1iscontradicted,thenthecondition 1 4 2 +1+ 1 + 1 2 1 n +1isalsocontradicted. Claim4.9 2 +1 1 + 1 1 4 2 +1+ 1 + 1 2 : Proof: Let 1 + 1 = 2 +1+ t ,where t isaninteger.Wehavethat 2 +1 2 + t 2 +1 2 +1 2 + t 2 +1+ t 2 4 : Factoringeachsideyields 2 +1 2 +1+ t 1 4 )]TJ/F15 11.9552 Tf 5.48 -9.684 Td [( 2 +2 2 +2 t 2 +2+ t 2 ; whichisthesameas 2 +1 1 + 1 1 4 2 +2+ t 2 = 1 4 2 +1+ 1 + 1 2 : Claim4.10 If u and v areverticesin G suchthat xu and yv arenotin E G ,then uv isnotin E G Proof: Assumeotherwise,andwithoutlossofgeneralitylet uv beanedgeof G 1 .Wemaythenexchangetheedges xy and uv withthenon-edges xu and yv in G 1 tocreateanotherrealizationof 1 .Since xu and yv arenotin G ,thisreducesthe numberofbadpairs,acontradiction. Claim4.10immediatelyimpliesthat I isanindependentsetin G Severaltimesthroughouttheproofweusetheobservationthat j N G [ y ] j 1 + 2 Thisboundfollowsfromourassumptionthat x;y isabadpairandthus x isa neighborof y inboth G 1 and G 2 .Nextweshowthat N G [ y ] 6 = V G 48

PAGE 59

Claim4.11 Y 6 = ; Proof: Towardcontradiction,supposethat N G [ y ]= V G .Thus j N G [ y ] j = n ,and therefore 1 + 2 n .Byassumption, 2 +1 1 + 1 1 n +1,whichimplies that 2 +1 1 + 1 1 1 + 2 +1 : Expandingandrearranging,thisyields 0 1 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.956 0 Td [( 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [( 1 +1 : However, 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 2 < 0and )]TJ/F19 11.9552 Tf 9.299 0 Td [( 1 +1 0,acontradiction. Consequently, N G [ y ] 6 = V G Claim4.12 Y isindependentin G 1 Proof: Otherwise,supposetherearevertices u and v in Y thatformanedge in G 1 .ByClaim4.10,both u and v mustbeadjacentto x .Ifthereissomevertex z 2 Q 1 y ,thenremovingtheedges uv xy ,and yz from G 1 andaddingthenonedges yu yv ,and xz to G 1 wouldcreateanotherrealizationof G 0 1 of 1 suchthat b G 0 1 ;G 2
PAGE 60

N G 1 u N G [ x ] N G y Consequently,suppose w;w 0 2 N G 1 Y aresuchthat ww 0 = 2 E G .Let u 2 N G 1 w Y and u 0 2 N G 1 w 0 Y u and u 0 neednotbedistinct.Notethatwithout lossofgenerality x 6 = w since xw 0 2 E G .If u 2 I ,thenreplacingtheedges uw u 0 w 0 ,and xy in G 1 withthenon-edges xu yu 0 ,and ww 0 contradictstheminimality of b G 1 ;G 2 .Thus u= 2 I ,andlikewise u 0 = 2 I Next,assumethereissome z 2 Q 1 y .ByClaim4.10, uz= 2 E G .Remove theedges wu w 0 u 0 ,and yz from G 1 andaddtheedges ww 0 yu 0 ,and zu tocreatea realization G 0 1 of 1 with b G 0 1 ;G 2 = b G 1 ;G 2 .However,neither x nor y areadjacent toverticesin f z g[ I x;y ,whichcontradictsthemaximalityof I Itremainstoconsiderthecasewhere Q 1 y = ; .Similartotheproofof Claim4.12,since Q 1 y isempty, Q 1 x isempty,therefore u;u 0 2 Q 2 x andthere mustbeavertex z in Q 2 y .Alsonotethatsince u;u 0 2 Q 2 x theedges xu and xu 0 arein G 2 .Exchangingtheedges wu w 0 u 0 ,and xy in G 1 with ux andthenon-edges u 0 y and ww 0 createsanotherrealization G 0 1 of 1 suchthat u;x isa G 0 1 ;G 2 -bad pairand b G 0 1 ;G 2 = b G 1 ;G 2 .However,byClaim4.10 u isnotadjacenttoverticesin f z g[ I x;y ,and x isnotadjacenttoverticesin f z g[ I x;y .Therefore I u;x >I x;y .Hence, N G 1 Y [f x;y g isacliquein G Claim4.14 A 6 = ; Proof: Forsakeofcontradiction,suppose A isempty,andtherefore N G 1 Y = B .Since Y isindependentin G 1 wehavethat 1 j Y jj B j .Thus, n = j Y j + j N G [ y ] j j B j 1 + 1 + 2 : Weproceedbyshowingthat j B j 1 + 2 )]TJ/F15 11.9552 Tf 12.448 0 Td [(2,whichestablishesthedesired contradiction.Bythedenitionof Y y isnotadjacenttoverticesin Y ,andtherefore y= 2 B .If x 62 B ,then j B jj N G y j)-33(jf x gj 1 + 2 )]TJ/F15 11.9552 Tf 9.699 0 Td [(2.If x 2 B ,thensince x hasa 50

PAGE 61

neighborin Y Q 1 x 6 = ; .Byassumption j Q 1 x jj Q 1 y j ,thusthereissomevertex z in N G [ y ]notadjacentto x .Nowwehavethat j B jj N G [ y ] )-127(f y;z gj 1 + 2 )]TJ/F15 11.9552 Tf 10.812 0 Td [(2. Insertingthisupperboundof j B j intotheaboveinequalitywehavethat 1 n +1 1 +1 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : ByClaim4.9, 2 +1 1 + 1 2 +1+ 1 + 1 2 4 ; sothatthehypothesisofthetheoremyields 2 +1 1 + 1 1 +1 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; whichsimpliesto 2 1 + 1 < 1 1 + 2 : Combiningthe 2 termsandthe 1 terms,wehave 2 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 < 1 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; whichisacontradictionwhen 1 =1.Otherwise,itcontradictstheassumptionthat 1 2 ByClaim4.14, A 6 = ; andbyClaim4.13, N G 1 Y [f x;y g isacliquein G and therefore N G 1 Y [f x;y g R Claim4.15 Everyedgeof G 1 isincidentwith R Proof: Towardscontradictionlet zz 0 beanedgeof G 1 notincidentwith R .By Claim4.12weknowthat z and z 0 mustbein N G [ y ] )]TJ/F19 11.9552 Tf 10.987 0 Td [(R ,sothereexistvertices w and w 0 notnecessarilydistinctin A whicharenotadjacentto z and z 0 respectively. Also,wehavedistinctvertices u and u 0 in Y suchthat wu and w 0 u 0 areedgesin G 1 51

PAGE 62

Wecanremovetheedges zz 0 uw ,and u 0 w 0 from G 1 andaddthenon-edges wz w 0 z 0 ,and uu 0 toformarealization G 0 1 of 1 .Itispossiblethat,viathisedge-exchange, u;u 0 isabadpairof G 0 1 ;G 2 ,implyingthat b G 0 1 ;G 2 = b G 1 ;G 2 +1.However,the sets Q 1 x Q 2 x Q 1 y ,and Q 2 y arenotaectedbytheseexchanges.Now, Y is nolongerindependentin G 1 and x;y isstillabadpair.AsintheproofofClaim4.12 wenowexchangeedgestoobtainarealization G 00 1 of 1 suchthat x;y and u;u 0 are nolongerbadpairsandnootherbadpairsarecreated.Thus, b G 00 1 ;G 2
PAGE 63

whichisthesameas 1 n +1 < j R j 1 + 1 : Byourassumptionon j R j wehavethefollowingcontradiction, 1 n +1 < 2 +1 1 + 1 : Nowassumethat j R j = 2 +1+ t ,where t isapositiveinteger.Noticethat j N G [ y ] j 1 + 2 impliesthat j N G [ y ] )]TJ/F19 11.9552 Tf 11.955 0 Td [(R j 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 2 +1+ t = 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : As y hasnoneighborsin Y y hasatmost 1 )]TJ/F19 11.9552 Tf 12.133 0 Td [(t )]TJ/F15 11.9552 Tf 12.133 0 Td [(1neighborsof G 1 in V )]TJ/F19 11.9552 Tf 12.133 0 Td [(R .If thereisanothervertex w 2 R )]TJ/F19 11.9552 Tf 11.336 0 Td [(N G 1 Y ,then w alsohasnoneighborsin Y andthus hasatmost 1 )]TJ/F19 11.9552 Tf 12.194 0 Td [(t )]TJ/F15 11.9552 Tf 12.195 0 Td [(1neighborsof G 1 in V )]TJ/F19 11.9552 Tf 12.194 0 Td [(R .If R )]TJ/F19 11.9552 Tf 12.194 0 Td [(N G 1 Y = f y g ,then R is aclique.Inthiscase, x hasatmost 1 + 2 )-257(j R j neighborsof G 1 in V )]TJ/F19 11.9552 Tf 12.371 0 Td [(R .As 1 + 2 )-180(j R j = 1 )]TJ/F19 11.9552 Tf 11.456 0 Td [(t )]TJ/F15 11.9552 Tf 11.456 0 Td [(1,wehavethatthereareatleasttwoverticesin R withat most 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t )]TJ/F15 11.9552 Tf 11.955 0 Td [(1neighborsof G 1 in V )]TJ/F19 11.9552 Tf 11.955 0 Td [(R Eachoftheremainingverticesof R haveatmost 1 )]TJ/F19 11.9552 Tf 10.59 0 Td [(t neighborsof G 1 in V )]TJ/F19 11.9552 Tf 10.59 0 Td [(R Inparticular,if v 2 B ,then v hasoneneighborof G 1 to Y andatmost 1 )]TJ/F19 11.9552 Tf 12.154 0 Td [(t )]TJ/F15 11.9552 Tf 12.154 0 Td [(1 neighborsof G 1 to N G [ y ] )]TJ/F19 11.9552 Tf 11.962 0 Td [(R .If v 2 A ,then v isadjacenttoeveryvertexof A ,and thereforehasatmost 1 + 2 )-222(j R j +1neighborsof G 1 to V )]TJ/F19 11.9552 Tf 11.955 0 Td [(R ,whichis 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t Therefore,wehavethat e 1 R;V )]TJ/F19 11.9552 Tf 11.955 0 Td [(R 2 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ j R j)]TJ/F15 11.9552 Tf 17.933 0 Td [(2 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t = j R j 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 : Combiningthiswiththelowerboundof e 1 R;V )]TJ/F19 11.9552 Tf 11.955 0 Td [(R ,wehave 1 n +1 < j R j 1 + 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t : 53

PAGE 64

Since 2 +1+ t = j R j ,weexpandtherightsidetoobtain 1 n +1 < 2 +1 1 + 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t 2 +1 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 + 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(t 2 : If 2 +2 1 + 1 ,thenwecontradictourclaimthat 2 +1 1 + 1 1 n +1. Otherwise, 2 +2 < 1 + 1 .Inthiscase,therightsideismaximizedwhen t = 1 2 )]TJ/F15 11.9552 Tf 9.298 0 Td [( 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ 1 + 1 ,whichyields 1 n +1 < 2 +1+ 1 + 1 2 4 : Thiscontradictioncompletestheproof. WenextproveCorollary4.5. Proof: Byassumption 1 +1 2 +1 n +1.If 1 =1,thenneccessarily 2 +2 1 + 1 .Also,wehavethat 2 +1 1 + 1 = 2 +1 1 +1and 1 n +1= n +1.Therefore 2 +1 1 + 1 1 n +1. If 1 > 1,weconsidertwocases.Firstsuppose 2 +2 1 + 1 .Since 1 )]TJ/F15 11.9552 Tf 10.881 0 Td [(1 > 0 and 1 > 1,wehave 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 < 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 1 2 + 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 1 : Thisyields 1 2 + 1 2 + 1 + 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 < 1 1 2 + 1 2 + 1 1 ; whichisequivalentto 1 + 1 2 +1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 1 < 2 +1 1 +1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : 54

PAGE 65

Byassumptionthisisatmost n ,completingthiscase,asnowwehave 1 + 1 2 +1 n 1 +1 : Now,suppose 1 > 1and 2 +2 > 1 + 1 .Since 2 1 ,wehave 0 < 4 1 2 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 +8 1 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 +8 1 +3 2 2 +10 2 +3 : Withsomemanipulation,wehavethat 2 +1+2 1 2 4 2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 )]TJ/F15 11.9552 Tf 42.153 8.088 Td [(1 2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 < 2 +1 1 +1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : Byassumption, 2 +1 1 +1 n +1.Notingthatsince 2 +2 < 1 + 1 we havethat 2 +3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 1 ,andthat 1 + 1 2 1 ,wehavethefollowing 2 +1+ 1 + 1 2 4 n 1 +1 ; asdesired. Finally,wegivethestraightforwardproofthatCorollary4.5impliesCorollary4.6. Proof: For 1 > 1,since 1 2 ,wehavethat 1 + 2 2 2 and2 2 1 2 thus 1 2 + 1 + 2 2 1 2 : Byassumption,2 1 2
PAGE 66

tions.Ofinteresthereis discretetomography ,whichuseslow-dimensionalprojections toreconstructdiscreteobjects,suchastheatomicstructureofcrystallinelatticesand otherpolyatomicstructures. 4.4.1The k -colorTomographyProblem Numerouspapersc.f.[24,25,37,38]studythe k -colorTomographyProblem inwhichthegoalistocolortheentriesofan m n matrixusing k colorssothat eachrowandcolumnreceivesaprescribednumberofentriesofeachcolor.Thecolors representdierenttypesofatomsappearinginacrystal,andthenumberoftimesan atomappearsinagivenroworcolumnisgenerallyobtainedusinghighresolution transmissionelectronmicroscopes[57,77].Thisispreciselytheproblemofpacking thedegreesequencesof k bipartitegraphswithpartitesetsofsize m and n 4.4.2ASauer-Spencer-typeTheoremfortheDiscreteTomography Problem Asequence = a 1 ;:::;a r ; b 1 ;:::;b s is bigraphic ifthereisabipartitegraph G suchthat = G withpartitesets X and Y ,andthedegreesoftheverticesin X and Y are a 1 ;:::;a r and b 1 ;:::;b s ,respectively.Twobigraphicsequences, 1 = a 1 ;:::;a r ; b 1 ;:::;b s and 2 = a 1 ;:::;a r ; b 1 ;:::;b s packifthereexist edge-disjointbipartitegraphs G 1 and G 2 ,bothwithpartitesets X = f x 1 ;:::;x r g and Y = f y 1 ;:::;y s g ,suchthatfor j 2f 1 ; 2 g d G j x i = a j i for1 i r ,and d G j y i = b j i for1 i s ThefollowingisatomographicanaloguetoCorollary4.6. 56

PAGE 67

Theorem4.16 [19] Let 1 and 2 bebigraphicsequenceswithpartsofsizes r and s and i = i and i = i for i 2f 1 ; 2 g ,suchthat 1 2 and 1 1 .If 1 2 r + s 4 then 1 and 2 pack. Theothermainresultofthissection,whichtakes 1 intoaccount,improveson Theorem4.16when 1 3. Theorem4.17 [19] Let 1 and 2 bebigraphicsequenceswithpartsofsizes r and s and i = i and i = i for i 2f 1 ; 2 g ,suchthat 1 2 and 1 1 .If 1 2 1 r + s 8 then 1 and 2 pack. Asbefore,wesayavertexpair x;y isa badpairfor G 1 ;G 2 ora G 1 ;G 2 -bad pair if xy 2 E G 1 E G 2 Let 1 and 2 bebigraphicsequencesthatdonotpack,choose G 1 = G 1 and G 2 = G 2 tohavethefewestbadpairsamongallrealizationsof 1 and 2 andlet G = G 1 [ G 2 .Fixa G 1 ;G 2 -badpair x;y andlet X and Y bethepartitesetsof G ,where x 2 X and y 2 Y .Let I X = X )]TJ/F19 11.9552 Tf 12.344 0 Td [(N G y and I Y = Y )]TJ/F19 11.9552 Tf 12.345 0 Td [(N G x .Wenow havethefollowinglemmas,therstofwhichisanalogoustoClaim4.10. Lemma4.18 Theset I X [ I Y isindependent. Proof: Supposeotherwise,soinparticularlet z 2 I X and z 0 2 I Y suchthat zz 0 2 E G .Exchangingtheedges xy and zz 0 withthenon-edges zy and z 0 x decreases thenumberof G 1 ;G 2 -badpairs,contradictingthechoiceof G 1 and G 2 57

PAGE 68

Lemma4.19 Thesubgraphof G inducedby N G 1 I Y [ N G 1 I X [f x;y g isacomplete bipartitegraph. Proof: First,notethatbyLemma4.18andthedenitionof I Y x isadjacent toeveryvertexin N G 1 I X andlikewise, y isadjacenttoeveryvertexin N G 1 I Y Supposethenthatthereissome w 2 N G 1 I Y and w 0 2 N G 1 I X suchthat ww 0 is notanedgein G .Nowwehavethatthereissome z 0 2 I Y and z 2 I X suchthat wz 0 and w 0 z areedgesin G 1 .Exchangingtheedges w 0 z wz 0 ,and xy allin G 1 withthe non-edges ww 0 xz 0 ,and yz decreasesthenumberofbadpairsin G ,acontradiction. WearenowreadytoproveTheorems4.16and4.17. Proof:ofTheorem4.16 Observerstthateachvertexin N G 1 I X respectively N G 1 I Y canhaveatmost 1 neighborsin I X resp. I Y sothat j I X j + j I Y j 1 j N G 1 I X j + j N G 1 I Y j : Wefurtherhavethat n )]TJ/F15 11.9552 Tf 11.955 0 Td [( j N G x j + j N G y j j I X j + j I Y j ; and j N G 1 I Y j + j N G 1 I X jj N G x j + j N G y j)]TJ/F15 11.9552 Tf 17.933 0 Td [(2 2 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(4 : Takentogether,theseyieldthat n )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 1 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(4 ; so n 2 1 +1 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : 58

PAGE 69

As 1 2 n 4 ,itfollowsthat 2 1 2 2 1 + 1 2 + 1 + 2 )]TJ/F15 11.9552 Tf 11.956 0 Td [(2 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; sothat 1 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 2 2 1 )]TJ/F15 11.9552 Tf 11.956 0 Td [( 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : However,then 2 1 )]TJ/F15 11.9552 Tf 27.7 8.088 Td [(1 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; acontradiction,since 1 2 Proof:ofTheorem4.17 ByLemma4.18, I X and I Y areindependent,so everyvertexin I X [ I Y musthaveatleast 1 neighborsin N G 1 I Y [ N G 1 I X .Also, asinTheorem4.16,eachvertexin N G 1 I Y [ N G 1 I X hasatmost 1 neighborsin I X [ I Y .Therefore, 1 j I X j + j I Y j 1 j N G 1 I Y j + j N G 1 I X j sothat j I X j + j I Y j 1 1 j N G 1 I Y j + j N G 1 I X j : Again,wehavethat j N G 1 I Y j + j N G 1 I X jj N G x j + j N G y j)]TJ/F15 11.9552 Tf 17.933 0 Td [(2 2 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 : Let r + s = n ,sothat j I X j + j I Y j = n )]TJ/F15 11.9552 Tf 11.955 0 Td [( j N G x j + j N G y j : 59

PAGE 70

Combiningtheaboveequationsyields n )]TJ/F15 11.9552 Tf 11.956 0 Td [(2 1 + 2 +2 2 1 1 1 + 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 : Byisolating 2 1 n 2 1 + 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [( 1 + 2 1 + 1 1 + 1 2 : Noticethat 1 + 1 2 1 ,sowehave 1 n 4 1 2 + 1 )]TJ/F15 11.9552 Tf 13.151 8.087 Td [(2 1 + 1 1 + 1 : Byassumption, 2 1 n 8 1 ,so 2 2 2 1 n 8 1 2 + 1 )]TJ/F15 11.9552 Tf 13.151 8.088 Td [(2 1 + 1 1 + 1 ; whichimplies 2 1 )]TJ/F15 11.9552 Tf 13.151 8.088 Td [(2 1 + 1 1 + 1 : Since 2 1 + 1 1 + 1 > 0,and 2 1 ,wearriveatacontradiction,completingthe proof. 60

PAGE 71

5.FutureWorkandOpenProblems 5.1RainbowMatchingsinEdge-ColoredGraphs Recently,Theorems2.1and2.2havebeenimprovedbyLoandTan[64]and byGyarfasandSarkozy[39].Infact,theextensiontoedge-coloredgraphs,but notnecessarilyproperlyedge-coloredgraphs,hasbeenconsidered.Inthiscase,we considerthe minimumcolordegree ^ G ,whichistheminimumnumberofdistinct colorsatanyvertexinagraph G .Theboundsinthisrealmhadbeenontheorder of ^ 2 see[58]untilthefollowingresult. Theorem5.1 [64] Let G beanedge-coloredgraphwithminimumcolordegree ^ .If n 4 ^ )]TJ/F15 11.9552 Tf 12.063 0 Td [(4 for ^ 4 or n 4 ^ )]TJ/F15 11.9552 Tf 12.064 0 Td [(3 for ^ 3 ,then G containsarainbowmatchings ofsize ^ Itisworthnotinghowever,thattheproofforTheorem5.1usesextremaltechniquestoshowexistence,andtherelevanceofanalgorithmremains,especiallyin lightofthefollowingcomplexityresultsforrainbowmatchings. Theorem5.2 [52] Givenanedge-coloredgraph G andinteger k ,itisNP-complete todetermineif G containsarainbowmatchingwithatleast k edges,evenwhen G is anedge-coloredbipartitegraph. Theorem5.3 [61] Givenanedge-coloredgraph G ,determiningthesizeofthelargest rainbowmatchingisAPX-complete,evenwhen G is 1.anedge-coloredcompletegraph, 2.aproperlyedge-coloredpath, 3.aproperlyedge-colored P 8 -freetreeinwhicheverycolorisusedatmosttwice, 4.aproperlyedge-colored P 5 -freelinearforestinwhicheverycolorisusedatmost twice, 61

PAGE 72

5.aproperlyedge-colored P 4 -freebipartitegraphinwhicheverycolorisusedat mosttwice. Giventheseresults,ouralgorithm,whichrunsin O j V G j 2 -time,isquitepowerful. 5.2OpenProblemsandConjecturesRegarding 2 -factorswitha BoundedNumberofComponents Theorem3.16impliesthatnominimumdegreeconditionon1-,2-,and3connectedclaw-freegraphswillensuretheexistenceofaneven2-factor.For4connectedclaw-freegraphs,welooktothewell-knownconjectureofMatthewsand Sumner[67]. Conjecture5.4TheMatthewsSumnerConjecture If G isa 4 -connectedclawfreegraph,then G ishamiltonian. Thisconjecturehasseveralequivalences,allofwhichremainopen.Everyline graphisclaw-free,andthusThomassenconjecturedthefollowing. Conjecture5.5 [81] Every 4 -connectedlinegraphishamiltonian. Aclosedtrailis dominating providedeveryedgehasanendpointonthetrail.A snark isa2-edge-connected,3-regulargraphthatisnot3-edge-colorablewithgirthat least5andnonon-trivial3-edgecut.Thefollowingconjecture,seeminglyunrelatedto Conjectures5.4and5.5,isalsoequivalenttotheseconjectures,asshownbyBroersma etal.[8]. Conjecture5.6 [8] Everysnarkcontainsadominatingcycle. Ahamiltoniancycleinagraphofevenorderisaneven2-factor.Thusinasimilar veinastheabove,wemakethefollowingconjecture. Conjecture5.7 [18] If G isa 4 -connected,claw-freegraphofevenorder,then G hasaneven 2 -factorifandonlyif G ishamiltonian. 62

PAGE 73

WealsoconjecturethefollowingextensionofTheorem3.4,andinparticular Corollary3.10. Conjecture5.8 [18] If G isa k -connected,claw-freegraphofevenorderatleast 2 k then G has k disjoint 1 -factorsifandonlyif cl G has k disjoint 1 -factors. For k 3,theconditionthat G is k -connectedinConjecture5.8isnecessary.To seethis,considerthegraph G obtainedbyconnectingavertex v to k )]TJ/F15 11.9552 Tf 11.911 0 Td [(1verticesin anoddcliqueoforderatleast2 k )]TJ/F15 11.9552 Tf 12.071 0 Td [(1.Theclosureof G iscomplete,but v doesnot havesucientdegreein G tobein k disjoint1-factors. 5.3DegreeSequenceandMixedPackingProblems Mixedpacking referstoamixtureofgraphpackingandsequencepackingwhere weconsideraxedgraph G andagraphicsequence .Ingeneral, G packs with ifthereissomerealization G 0 of suchthat G and G 0 pack.Inthiscase,vertex permutationsof G areallowedinordertopack G and G 0 .Wehavethefollowing conjecture. Conjecture5.9 [20] Let G bean n -vertexgraphand = d 1 ;d 2 ;:::;d n bean n termgraphicsequencewith themaximumtermof and G themaximumdegree in G .If G +1 +1 n +1 ; then G and pack. Conjecture5.9isamixedpackinganaloguetotheBollobas-Eldridge-Catlingraph packingconjecture,andisstrongerthanCorollary4.5sincewecanuse2-switchesin bothsequenceswhenpackingtwosequences,butnolongerhavethisexibilitywith mixedpacking. Intheeventthatwehaveaxedgraph G andgraphicsequence suchthat theverticesof G arexedwithrespectto ,meaningthat V G = f v 1 ;:::;v n g and 63

PAGE 74

d v i = d i ,then G' -packs with .Thisisamorerestrictiveversionofmixed packing,andsodeterminingconditionssuchthat G and -packwouldalsobe interesting. 64

PAGE 75

REFERENCES [1]M.AignerandS.Brandt,Embeddingarbitrarygraphsofmaximumdegreetwo, J.LondonMath.Soc. 28 ,39{51. [2]J.AkiyamaandM.Kano,FactorsandFactorizationsofGraphs:ProofTechniquesinFactorTheory, LectureNotesinMathematicsVol.2031 ,Springer,2011. [3]R.E.L.Aldred,Y.Egawa,J.Fujisawa,K.Ota,andA.Saito,Theexistenceofa 2-factorin K 1 ;n -freegraphswithlargeconnectivityandlargeedge-connectivity, J.GraphTheory 68 ,77{89. [4]N.AlonandE.Fischer,2-factorsindensegraphs, DiscreteMath. 152 13{23. [5]D.Bauer,H.J.Broersma,J.vandenHeuvel,N.Kahl,A.Nevo,E.Schmeichel, D.R.Woodall,andM.Yatauro,ASurveyofBestMonotoneDegreeConditions forGraphProperties,submitted. arXiv:1405.5760v1 [6]C.Berge,FarbungvonGraphen,derensamtlichebzw.derenungeradeKreise starrsind, Wiss.Z.Martin-Luther-Univ.Halle-WittenbergMath.-Natur.Reihe 10 ,114. [7]B.BollobasandS.E.Eldridge,Packingsofgraphsandapplicationstocomputationalcomplexity, J.Combin.TheorySer.B 25 ,105{124. [8]H.Broersma,G.Fijavz,T.Kaiser,R.Kuzel,Z.Ryjacek,andP.Vrana,Contracitiblesubgraphs,Thommasen'sconjectureandthedominatingcycleconjectureforsnarks, DiscreteMath. 308 ,6064{6077. [9]R.A.BrualdiandH.J.Ryser,CombinatorialMatrixTheory, Encyclopediaof MathematicsanditsApplications ,CambridgeUniversityPress,Cambridge,UK, 1991. [10]A.Busch,M.Ferrara,S.Hartke,andM.Jacobson,Ramsey-typenumbersfor degreesequences, Graphs.Comb. 30 ,847{859. [11]A.Busch,M.Ferrara,M.Jacobson,H.Kaul,S.Hartke,andD.B.West,Packing ofGraphic n -tuples, J.GraphTheory 70 ,29{39. [12]P.Catlin,Embeddingsubgraphsandcoloringgraphsunderextremaldegreeconditions, Ph.D.Thesis ,OhioStateUniversity,1976. [13]S.A.ChoudumandM.S.Paulraj,Regularfactorsin K 1 ; 3 -freegraphs, J.Graph Theory 15 ,no.3,259{265. 65

PAGE 76

[14]M.Chudnovsky,N.Robertson,P.Seymour,andR.Thomas,Thestrongperfect graphtheorem, Ann.ofMath. 164 ,51{226. [15]V.Chvatal,OnHamilton'sideals, J.Combin.TheorySer.B 12 ,163{168. [16]H.CorradiandA.Hajnal,OntheMaximalNumberofIndependentCircuitsin aGraph, ActaMath.Hung. 14 ,423{439. [17]B.Csaba,A.Shokoufandeh,andE.Szemeredi,ProofofaconjectureofBollobas andEldridgeforgraphsofmaximumdegreethree, Combinatorica 23 35{72. [18]J.Diemunsch,M.Ferrara,S.Graeo,andT.Morris,On2-factorswithabounded numberofoddcomponents, DiscreteMath. 323 ,35{42. [19]J.Diemunsch,M.Ferrara,S.Jahanbekam,andJ.Shook,Extremaltheoremsfor degreesequencepackingandthe2-colordiscretetomographyproblem,submitted. [20]J.Diemunsch,M.Ferrara,S.Jahanbekam,andJ.Shook,Extremaltheoremsfor mixedpacking,inprogress. [21]J.Diemusch,M.Ferrara,A.Lo,C.Moatt,F.Pfender,andP.S.Wenger,Rainbowmatchingsofsize inproperlyedge-coloredgraphs, Electron.J.Combin. 19 ,no.2,Paper52,11pp. [22]R.Diestel,GraphTheory, GraduateTextsinMathematics 173 ,Springer-Verlag, NewYork,1997. [23]G.A.Dirac,Sometheoremsonabstractgraphs, Proc.LondonMath.Soc. 2 ,69{81. [24]P.DulioandC.Peri,Discretetomographyandplanepartitions. Adv.inAppl. Math. 50 ,390{408. [25]C.Durr,F.Gui~nez,andC.Matamala,Reconstructing3-coloredgridsfromhorizontalandverticalprojectionsisNP-hard:asolutiontothe2-atomproblemin discretetomography, SIAMJ.DiscreteMath. 26 ,330{352. [26]Z.DvorakandB.Mohar,Chromaticnumberandcompletegraphsubstructures fordegreesequences, Combinatorica 33 ,513{529. [27]Y.EgawaandK.Ota,Regularfactorsin K 1 ;n -freegraphs, J.GraphTheory 15 ,no.3,337{344. [28]P.Erd}osandT.Gallai,Graphswithprescribeddegrees, MatematikiLapor 11 ,264{274inHungarian. [29]P.Erd}osandM.Simonovits,Alimittheoremingraphtheory, StudiaSci.Math. Hungar 1 ,51{57. 66

PAGE 77

[30]P.Erd}osandA.M.Stone,Onthestructureoflineargraphs, Bull.Amer.Math. Soc. 52 ,1087{1091. [31]J.R.Faudree,R.J.Faudree,andZ.Ryjacek,Forbiddensubgraphsthatimply 2-factors, DiscreteMath. 308 ,no.9,1571{1582. [32]M.Ferrara,T.LeSaulnier,C.MoattandP.Wenger,OntheSumNecessaryto EnsureaDegreeSequenceisPotentially H -Graphic,toappearin Combinatorica. [33]J.FujisawaandA.Saito,Apairofforbiddensubgraphsand2-factors, Combin. Probab.Comput. 21 ,149{158. [34]R.Gould,UpdatingtheHamiltonianproblem{asurvey, J.GraphTheory 15 ,121{157. [35]R.Gould,Advancesonthehamiltonianproblem{asurvey, GraphsComb. 19 ,7-52. [36]R.J.GouldandM.S.Jacobson,ForbiddensubgraphsandHamiltonianproperties ofgraphs, DiscreteMath. 42 -3189{196,1982. [37]P.Gritzmann,B.Langfeld,andM.Wiegelmann,Uniquenessindiscretetomography:threeremarksandacorollary, SIAMJ.DiscreteMath. 25 ,1589{ 1599. [38]F.Gui~nez,C.Matamala,andS.Thomasse,Realizingdisjointdegreesequences ofspanatmosttwo:Atractablediscretetomographyproblem, DiscreteApplied Math. 159 ,23{30. [39]A.GyarfasandG.Sarkozy,Rainbowmatchingsandcycle-freepartialtransversalsofLatinsquares, DiscreteMath. 327 ,96{102. [40]R.HaggkvistandS.McGuinness,Doublecoversofcubicgraphswithoddness4, J.Combin.TheorySer.B 93 ,251{277. [41]A.HajnalandE.Szemeredi,ProofofaConjectureofErd}os,in Combinatorial TheoryandItsApplications,II P.Erd}os,andV.T.Sos,Eds.,ColloquiaMathematicaSocietatisJanosBolyai,North-Holland,Amsterdam/London,1970. [42]S.L.Hakimi,Ontherealizabilityofasetofintegersasdegreesofverticesofa graph, J.SIAMAppl.Math 10 ,496{506. [43]S.L.HakimiandE.Schmeichel,Graphsandtheirdegreesequences:Asurvey.In TheoryandApplicationsofGraphs ,volume642of LectureNotesinMathematics SpringerBerlin/Heidelberg,1978,225{235. [44]F.HararyandC.St.J.A.Nash-Williams,OnEulerianandHamiltoniangraphs andlinegraphs, Canad.Math.Bull. 8 ,701{709. 67

PAGE 78

[45]V.Havel,AremarkontheexistenceofnitegraphsCzech., CasopisP est:Mat: 80 ,477{480. [46]A.J.W.Hilton,Factorizationsofregulargraphsofhighdegree, J.GraphTheory 9 ,no.1,193{196. [47]D.G.HomanandC.A.Rodger,Onthenumberofedge-disjointonefactorsand theexistenceof k -factorsincompletemultipartitegraphs, DiscreteMath. 160 ,no.1-3,177{187. [48]I.Holyer,TheNP-completenessofedge-coloring, SIAMJ.Comput. 10 718{720. [49]X.Hou,Ontheperfectmatchingsofnearregulargraphs. GraphsCombin. 27 ,865{869. [50]A.Huck,Oncycle-doublecoversofgraphsofsmalloddness, DiscreteMath. 229 ,125-165. [51]A.HuckandM.Kochol,Note:FiveCycleDoubleCoversofSomeCubicGraphs, J.Combin.TheorySer.B 64 ,119{125. [52]A.Itai,M.Rodeh,andS.L.Tanimoto,Somematchingproblemsforbipartite graphs, J.Assoc.Comput.Mach. 25 ,517{525. [53]M.KanoandX.Li,Monochromaticandheterochromaticsubgraphsinedgecoloredgraphs{asurvey, GraphsCombin. 24 ,237{263. [54]H.KaulandA.Kostochka,Extremalgraphsforagraphpackingtheoremof SauerandSpencer, Combin.Probab.Comput. 16 ,no.3,409{416. [55]H.Kaul,A.Kostochka,andG.Yu,OnagraphpackingconjecturebyBollobas, EldridgeandCatlin, Combinatorica 28 ,469{485. [56]H.Kierstead,A.Kostochka,andG.Yu,Extremalgraphpackingproblems:OretypeversusDirac-type, LondonMathematicalSocietyLectureNoteSeries 365 CambridgeUniv.Press,Cambridge,2009. [57]C.Kisielowski,P.Schwander,F.Baumann,M.Seibt,Y.Kim,andA.Ourmazd, Anapproachtoquantitatehighresolutiontransmissionelectronmicroscopyof crystallinematerials, Ultramicroscopy 58 ,131{155. [58]A.Kostochka,F.Pfender,andM.Yancey,Largerainbowmatchingsinlarge graphs, arXiv:1204.3193 ,. [59]A.KostochkaandM.Yancey,Largerainbowmatchingsinedge-colouredgraphs, Combin.Probab.Comput. 21 ,255{263. [60]S.Kundu,The k -factorconjectureistrue, DiscreteMath. 6 ,367{376. 68

PAGE 79

[61]V.B.LeandF.Pfender,Complexityresultsforrainbowmatchings, Theoret. Comput.Sci. 524 ,27{33. [62]T.D.LeSaulnier,C.Stocker,P.S.Wenger,andD.B.West,Rainbowmatchingin edge-coloredgraphs, Electron.J.Combin. 17 ,Note26. [63]J.LiandJ.Yin,AvariationofaconjectureduetoErd}osandSos, ActaMath. Sin. 25 ,795{802. [64]A.LoandT.S.Tan,Anoteonlargerainbowmatchingsinedge-colouredgraphs, GraphsandCombin. 30 ,389{393. [65]L.Lovasz,Acharacterizationofperfectgraphs, J.CombinatorialTheorySer. B 13 ,95{98. [66]L.Lovasz,Valenciesofgraphswith1-factors, PeriodicaMath.Hung. 5 149{151. [67]M.M.MatthewsandD.P.Sumner,Hamiltonianresultsin K 1 ; 3 -freegraphs, J. GraphTheory 8 ,no.1,139{146. [68]V.V.Mkrtchyan,V.L.Musoyan,andA.V.Tserunyan,Onedge-disjointpairsof matchings, DiscreteMath. 308 5823{5828. [69]V.V.Mkrtchyan,andS.S.Petrosyan,andG.N.Vardanyan,Ondisjointmatchingsincubicgraphs, DiscreteMath. 310 1588{1613. [70]A.R.Rao,Thecliquenumberofagraphwithagivendegreesequence.In ProceedingsoftheSymposiumonGraphTheory ,volume4of ISILectureNotes MacmillanofIndia,NewDelhi,1979,251{267. [71]S.B.Rao,Asurveyofthetheoryofpotentially P -graphicandforcibly P -graphic degreesequences.In Combinatoricsandgraphtheory ,volume885of Lecture NotesinMath. ,Springer,Berlin,1981,417{440. [72]N.RobertsonandZ.Song,Hadwigernumberandchromaticnumberfornear regulardegreesequences, J.GraphTheory 64 ,175{183. [73]Z.Ryjacek,Onaclosureconceptinclaw-freegraphs, J.Combin.TheorySer.B 70 ,no.2,217{224. [74]Z.Ryjacek,A.Saito,andR.H.Schelp,Closure,2-factors,andcyclecoveringsin claw-freegraphs, J.GraphTheory 32 ,no.2,109{117. [75]H.J.Ryser,NeuereProblemederKombinatorikinVortrageuberKombinatorik Oberwolfach",MathematischesForschungsinstitutOberwolfach,July1967,24{ 29. [76]N.SauerandJ.Spencer,Edgedisjointplacementofgraphs, J.Combin.Theory Ser.B 25 ,295{302. 69

PAGE 80

[77]P.Schwander,C.Kisielowski,M.Seigt,F.Baumann,Y.Kim,andA.Ourmazd, Mappingprojectedpotentialinterfacialroughnessandcompositioningeneral crystallinesolidsbyquantitativetransmissionelectronmicroscopy, PhysicalReviewLetters 71 ,4150{4153. [78]P.Seymour,Sumsofcircuits,in:J.A.Bondy,U.S.R.MurtyEds., GraphTheory andRelatedTopics ,AcademicPress,NewYork,1978,pp.341{355. [79]S.K.Stein,TransversalsofLatinsquaresandtheirgeneralizations, PacicJ. Math. 59 ,567{575. [80]G.Szekeres,Polyhedraldecompositionsofcubicgraphs, J.Austrail.Math.Soc. 8 ,367{387. [81]C.Thomassen,Reectionsongraphtheory, J.GraphTheory 10 ,309{ 324. [82]P.Turan,EineExtremalaufgabeausdergraphentheorie, Mat.Fiz.Lapok 48 ,436{452. [83]G.Wang,Rainbowmatchingsinproperlyedge-coloredgraphs, Electron.J.Combin. 18 ,Paper162. [84]G.WangandH.Li,Heterochromaticmatchingsinedge-coloredgraphs, Electron. J.Combin. 15 ,ResearchPaper138. [85]G.Wang,J.Zhang,andG.Liu,Existenceofrainbowmatchingsinproperly edge-coloredgraphs, Front.Math.China 7 ,543{550. [86]I.M.Wanless,TransversalsinLatinsquares:asurvey, SurveysinConbinatorics 2011 392 ,CambridgeUniv.Press,Cambridge,403{437. [87]D.B.West, Introductiontographtheory .PrenticeHall,Inc.,UpperSaddleRiver, NJ,1996. [88]M.Wozniak,PackingofGraphs, DissertationesMath. 362 ,78pp. [89]H.Yap,PackingofGraphs:Asurvey, DiscreteMath. 72 ,395{404. [90]K.Yoshimoto,Onthenumberofcomponentsin2-factorsofclaw-freegraphs, DiscreteMath. 307 ,no.22,2808{2819. [91]C.Q.ZhangandY.J.Zhu.Factorizationsofregulargraphs, J.Combin.Theory Ser.B 56 ,no.1,74{89. 70