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

Béla Bollobás: Modern Graph Theory

Published $\text {1998}$, Springer

ISBN 978-0387984889

Subject Matter

• Graph Theory

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