图论

Preface

1.TheBasics

1.1Graphs*

1.2Thedegreeofavertex*

1.3Pathsandcycles*

1.4Connectivity*

1.5Treesandforests*

1.6Bipartitegraphs*

1.7Contractionandminors*

1.8Eulertours*

1.9Somelinearalgebra

1.10Othernotionsofgraphs

Exercises

Notes

2.Matching,CoveringandPacking

2.1Matchinginbipartitegraphs*

2.2Matchingingeneralgraphs(*)

2.3Packingandcovering

2.4Tree-packingandarboricity

2.5Pathcovers

Exercises

Notes

3.Connectivity

3.12-Connectedgraphsandsubgraphs*

3.2Thestructureof3-connectedgraphs(*)

3.3Mengerstheorem*

3.4Maderstheorem

3.5Linkingpairsofvertices(*)

Exercises

Notes

4.PlanarGraphs

4.1Topologicalprerequisites*

4.2Planegraphs*

4.3Drawings

4.4Planargraphs:Kuratowskistheorem*

4.5Algebraicplanaritycriteria

4.6Planeduality

Exercises

Notes

5.Colouring

5.1Colouringmapsandplanargraphs*

5.2Colouringvertices*

5.3Colouringedges*

5.4Listcolouring

5.5Perfectgraphs

Exercises

Notes

6.Flows

6.1Circulations(*)

6.2Flowsinnetworks*

6.3Group-valuedflows

6.4k-Flowsforsmallk

6.5Flow-colouringduality

6.6Tuttesflowconjectures

Exercises

Notes

7.ExtremalGraphTheory

7.1Subgraphs*

7.2Minors(*)

7.3Hadwigersconjecture*

7.4Szemeredisregularitylemma

7.5Applyingtheregularitylemma

Exercises

Notes

8.InfiniteGraphs

8.1Basicnotions,factsandtechniques*

8.2Paths,trees,andends(*)

8.3Homogeneousanduniversalgraphs*

8.4Connectivityandmatching

8.5Thetopologicalendspace

Exercises

Notes

9.RamseyTheoryforGraphs

9.1Ramseysoriginaltheorems*

9.2Ramseynumbers(*)

9.3InducedRamseytheorems

9.4Ramseypropertiesandconnectivity(*)

Exercises

Notes

10.HamiltonCycles

10.1Simplesufficientconditions*

10.2Hamiltoncyclesanddegreesequences*

10.3Hamiltoncyclesinthesquareofagraph

Exercises

Notes

11.RandomGraphs

11.1Thenotionofarandomgraph*

11.2Theprobabilisticmethod*

11.3Propertiesofalmostallgraphs*

11.4Thresholdfunctionsandsecondmoments

Exercises

Notes

12.Minors,TreesandWQO

12.1Well-quasi-ordering*

12.2Thegraphminortheoremfortrees*

12.3Tree-decompositions

12.4Tree-widthandforbiddenminors

12.5Thegraphminortheorem(*)

Exercises

Notes

A.Infinitesets

B.Surfaces

Hintsforalltheexercises

Index

Symbolindex

　　Almosttwodecadeshavepassedsincetheappearanceofthosegraphtheorytextsthatstillsettheagendaformostintroductorycoursestaughttoday.Thecanoncreatedbythosebookshashelpedtoidentifysomemainfieldsofstudyandresearch,andwilldoubtlesscontinuetoinfluencethedevelopmentofthedisciplineforsometimetocome.