Book:Béla Bollobás/Modern Graph Theory

From ProofWiki
Jump to: navigation, search

Béla Bollobás: Modern Graph Theory

Published $1998$, Springer

ISBN 978-0387984889.


Subject Matter


Contents

Apologia
Preface
I Fundamentals
I.1 Definitions
I.2 Paths, Cycles, and Trees
I.3 Hamilton Cycles and Euler Circuits
I.4 Planar Graphs
I.5 An Application of Euler Trails to Algebra
I.6 Exercises
II Electrical Networks
II.1 Graphs and Electrical Networks
II.2 Squaring the Square
II.3 Vector Spaces and Matrices Associated with Graphs
II.4 Exercises
II.5 Notes
III Flows, Connectivity and Matching
III.1 Flows in Directed Graphs
III.2 Connectivity and Menger's Theorem
III.3 Matching
III.4 Tutte's 1-Factor Theorem
III.5 Stable Matchings
III.6 Exercises
III.7 Notes
IV Extremal Problems
IV.1 Paths and Cycles
IV.2 Complete Subgraphs
IV.3 Hamilton Paths and Cycles
IV.4 The Structure of Graphs
IV.5 Szemerédi's Regularity Lemma
IV.6 Simple Applications of Szemerédi's Lemma
IV.7 Exercises
IV.8 Notes
V Colouring
V.1 Vertex Colouring
V.2 Edge Colouring
V.3 Graphs on Surfaces
V.4 List Colouring
V.5 Perfect Graphs
V.6 Exercises
V.7 Notes
VI Ramsey Theory
VI.1 The Fundamental Ramsey Theorems
VI.2 Canonical Ramsey Theorems
VI.3 Ramsey Theory for Graphs
VI.4 Ramsey Theory for Integers
VI.5 Subsequences
VI.6 Exercises
VI.7 Notes
VII Random Graphs
VII.1 The Basic Models—The Use of the Expectation
VII.2 Simple Properties of Almost All Graphs
VII.3 Almost Determined Variables—The Use of the Variance
VII.4 Hamilton Cycles—The Use of Graph Theoretic Tools
VII.5 The Phase Transition
VII.6 Exercises
VII.7 Notes
VIII Graphs, Groups and Matrices
VIII.1 Cayley and Schreier Diagrams
VIII.2 The Adjacency Matrix and the Laplacian
VIII.3 Strongly Regular Graphs
VIII.4 Enumeration and Pólya's Theorem
VIII.5 Exercises
IX Random Walks on Graphs
IX.1 Electrical Networks Revisited
IX.2 Electrical Networks and Random Walks
IX.3 Hitting Times and Commute Times
IX.4 Conductance and Rapid Mixing
IX.5 Exercises
IX.6 Notes
X The Tutte Polynomial
X.1 Basic Properties of the Tutte Polynomial
X.2 The Universal Form of the Tutte Polynomial
X.3 The Tutte Polynomial in Statistical Mechanics
X.4 Special Values of the Tutte Polynomial
X.5 A Spanning Tree Expansion of the Tutte Polynomial
X.6 Polynomials of Knots and Links
X.7 Exercises
X.8 Notes
Symbol Index
Name Index
Subject Index