内容

目次

Preface1: The Basics 1.1 Graphs* 1.2 The degree of a vertex*1.3 Paths and cycles* 1.4 Connectivity* 1.5 Trees and forests* 1.6 Bipartite graphs* 1 7 Contraction and minors* 1.8 Euler tours* 1.9 Some linear algebra1.10 Other notions of graphsExercisesNotes2: Matching, Covering and Packing2.1 Matching in bipartite graphs*2.2 Matching in general graphs(*)2.3 Packing and covering2.4 Tree-packing and arboricity 2.5 Path covers ExercisesNotes3: Connectivity 3.1 2-Connected graphs and subgraphs* 3.2 The structure of 3-connected graphs(*) 3.3 Menger’s theorem* 3.4 Mader’s theorem 3.5 Linking pairs of vertices(*)Exercises Notes 4: Planar Graphs 4.1 Topological prerequisites* 4.2 Plane graphs*4.3 Drawings 4.4 Planar graphs: Kuratowski’s theorem* 4.5 Algebraic planarity criteria 4.6 Plane duality Exercises Notes 5: Colouring 5.1 Colouring maps and planar graphs* 5.2 Colouring vertices* 5.3 Colouring edges* 5.4 List colouring 5.5 Perfect graphs Exercises Notes 6: Flows6.1 Circulations(*)6.2 Flows in networks* 6.3 Group-valued flows6.4 k-Flows for small k6.5 Flow-colouring duality6.6 Tutte’s flow conjecturesExercisesNotes 7: Extremal Graph Theory7.1 Subgraphs* 7.2 Minors(*) 7.3 Hadwiger’s conjecture*7.4 Szemerédi’s regularity lemma7.5 Applying the regularity lemmaExercisesNotes8: Infinite Graphs8.1 Basic notions, facts and techniques* 8.2 Paths, trees, and ends(*)8.3 Homogeneous and universal graphs* 8.4 Connectivity and matching 8.5 The topological end space Exercises Notes9: Ramsey Theory for Graphs9.1 Ramsey’s original theorems*9.2 Ramsey numbers(*)9.3 Induced Ramsey theorems9.4 Ramsey properties and connectivity(*)ExercisesNotes10: Hamilton Cycles10.1 Simple sufficient conditions*10.2 Hamilton cycles and degree sequences*10.3 Hamilton cycles in the square of a graphExercisesNotes11: Random Graphs11.1 The notion of a random graph* 11.2 The probabilistic method* 11.3 Properties of almost all graphs*1 1.4 Threshold functions and second momentsExercisesNotes 12: Minors, Trees and WQO 12.1 Well-quasi-ordering* 12.2 The graph minor theorem for trees* 12.3 Tree-decompositions 12.4 Tree-width and forbidden minors 12.5 The graph minor theorem(*)Exercises NotesA. Infinite sets B. Surfaces Hints for all the exercises Index Symbol index * Sections marked by an asterisk are recommended for a first course. Of sections marked (*), the beginning is recommended for a first course.