Modern Graph Theory

Front Cover
Springer Science & Business Media, Jan 1, 1998 - Computers - 394 pages
3 Reviews
The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed account of newer topics, including Szemer\'edi's Regularity Lemma and its use, Shelah's extension of the Hales-Jewett Theorem, the precise nature of the phase transition in a random graph process, the connection between electrical networks and random walks on graphs, and the Tutte polynomial and its cousins in knot theory. In no other branch of mathematics is it as vital to tackle and solve challenging exercises in order to master the subject. To this end, the book contains an unusually large number of well thought-out exercises: over 600 in total. Although some are straightforward, most of them are substantial, and others will stretch even the most able reader.
  

What people are saying - Write a review

User Review - Flag as inappropriate

a really bad book for study, since it does not contain any solutions to its exercises.

User Review - Flag as inappropriate

The online version of this text is badly distorted as to make it unreadable.

Contents

Fundamentals
xv
I2 Paths Cycles and Trees
xxii
I3 Hamilton Cycles and Euler Circuits
4
I4 Planar Graphs
10
I5 An Application of Euler Trails to Algebra
15
I6 Exercises
18
Electrical Networks
29
II2 Squaring the Square
36
VI3 Ramsey Theory For Graphs
182
VI4 Ramsey Theory for Integers
187
VI5 Subsequences
195
VI6 Exercises
198
VI7 Notes
203
Random Graphs
205
VII1 The Basic ModelsThe Use of the Expectation
206
VII2 Simple Properties of Almost All Graphs
215

II3 Vector Spaces and Matrices Associated with Graphs
41
II4 Exercises
48
II5 Notes
56
Hows Connectivity and Matching
57
III1 Flows in Directed Graphs
58
III2 Connectivity and Mengers Theorem
63
III3 Matching
66
III4 Tuttes 1Factor Theorem
72
III5 Stable Matchings
75
III6 Exercises
81
III7 Notes
91
Extremal Problems
93
IV1 Paths and Cycles
94
IV2 Complete Subgraphs
98
IV3 Hamilton Paths and Cycles
105
IV4 The Structure of Graphs
110
IV5 Szemeredis Regularity Lemma
114
IV6 Simple Applications of Szemeredis Lemma
120
IV7 Exercises
125
IV8 Notes
132
Colouring
135
V1 Vertex Colouring
136
V2 Edge Colouring
142
V3 Graphs on Surfaces
144
V4 List Colouring
151
V5 Perfect Graphs
155
V6 Exercises
160
V7 Notes
167
Ramsey Theory
171
VI1 The Fundamental Ramsey Theorems
172
VI2 Canonical Ramsey Theorems
179
VII3 Almost Determined Variables The Use of the Variance
218
VII4 Hamilton CyclesThe Use of Graph Theoretic Tools
226
VII5 The Phase Transition
230
VII6 Exercises
236
VII7 Notes
241
Graphs Groups and Matrices
243
VIII1 Cayley and Schreier Diagrams
244
VIII2 The Adjacency Matrix and the Laplacian
252
VIII3 Strongly Regular Graphs
260
VIII4 Enumeration and Polyas Theorem
266
VIII5 Exercises
273
Random Walks on Graphs
285
IX1 Electrical Networks Revisited
286
IX2 Electrical Networks and Random Walks
291
IX3 Hitting Times and Commute Times
299
IX4 Conductance and Rapid Mixing
309
IX5 Exercises
317
IX6 Notes
323
The Tutte Polynomial
325
X1 Basic Properties of the Tutte Polynomial
326
X2 The Universal Form of the Tutte Polynomial
330
X3 The Tutte Polynomial in Statistical Mechanics
332
X4 Special Values of the Tutte Polynomial
335
X5 A Spanning Tree Expansion of the Tutte Polynomial
340
X6 Polynomials of Knots and Links
348
X7 Exercises
361
X8 Notes
367
Symbol Index
369
Name Index
373
Subject Index
377
Copyright

Common terms and phrases

Popular passages

Page vi - As long as a branch of science offers an abundance of problems, so long is it alive; a lack of problems foreshadows extinction or the cessation of independent development. Just as every human undertaking pursues certain objects, so also mathematical research requires its problems. It is by the solution of problems that the investigator tests the temper of his steel; he finds new methods and new outlooks, and gains a wider and freer horizon.

References to this book

All Book Search results »

Bibliographic information