Graph Theory

by Diestel, Reinhard

• ISBN13: 9783540261834
• ISBN10: 3540261834
• Edition: 3rd
• Format: Paperback
• Copyright: 2006-04-04
• Publisher: Springer Verlag

Summary

The third edition of this standard textbook of modern graph theory has been carefully revised, updated, and substantially extended. Covering all its major recent developments it can be used both as a reliable textbook for an introductory course and as a graduate text: on each topic it covers all the basic material in full detail, and adds one or two deeper results (again with detailed proofs) to illustrate the more advanced methods of that field. From the reviews of the first two editions (1997, 2000):"This outstanding book cannot be substituted with any other book on the present textbook market. It has every chance of becoming the standard textbook for graph theory." Acta Scientiarum Mathematiciarum"The book has received a very enthusiastic reception, which it amply deserves. A masterly elucidation of modern graph theory." Bulletin of the Institute of Combinatorics and its Applications"A highlight of the book is what is by far the best account in print of the Seymour-Robertson theory of graph minors." Mathematika". . . like listening to someone explain mathematics." Bulletin of the AMS

Table of Contents

Preface	vii
The Basics	1	(32)
Graphs	2	(3)
The degree of a vertex	5	(1)
Paths and cycles	6	(4)
Connectivity	10	(3)
Trees and forests	13	(4)
Bipartite graphs	17	(1)
Contraction and minors	18	(4)
Euler tours	22	(1)
Some linear algebra	23	(5)
Other notions of graphs	28	(5)
Exercises	30	(2)
Notes	32	(1)
Matching, Covering and Packing	33	(22)
Matching in bipartite graphs	34	(5)
Matching in general graphs	39	(5)
Packing and covering	44	(2)
Tree-packing and arboricity	46	(3)
Path covers	49	(6)
Exercises	51	(2)
Notes	53	(2)
Connectivity	55	(28)
2-Connected graphs and subgraphs	55	(2)
The structure of 3-connected graphs	57	(5)
Menger's theorem	62	(5)
Mader's theorem	67	(2)
Linking pairs of vertices	69	(14)
Exercises	78	(2)
Notes	80	(3)
Planar Graphs	83	(28)
Topological prerequisites	84	(2)
Plane graphs	86	(6)
Drawings	92	(4)
Planar graphs: Kuratowski's theorem	96	(5)
Algebraic planarity criteria	101	(2)
Plane duality	103	(8)
Exercises	106	(3)
Notes	109	(2)
Colouring	111	(28)
Colouring maps and planar graphs	112	(2)
Colouring vertices	114	(5)
Colouring edges	119	(2)
List colouring	121	(5)
Perfect graphs	126	(13)
Exercises	133	(3)
Notes	136	(3)
Flows	139	(24)
Circulations	140	(1)
Flows in networks	141	(3)
Group-valued flows	144	(5)
k-Flows for small k	149	(3)
Flow-colouring duality	152	(4)
Tutte's flow conjectures	156	(7)
Exercises	160	(1)
Notes	161	(2)
Extremal Graph Theory	163	(32)
Subgraphs	164	(5)
Minors	169	(3)
Hadwiger's conjecture	172	(3)
Szemeredi's regularity lemma	175	(8)
Applying the regularity lemma	183	(12)
Exercises	189	(3)
Notes	192	(3)
Infinite Graphs	195	(56)
Basic notions, facts and techniques	196	(8)
Paths, trees, and ends	204	(8)
Homogeneous and universal graphs	212	(4)
Connectivity and matching	216	(10)
The topological end space	226	(25)
Exercises	237	(7)
Notes	244	(7)
Ramsey Theory for Graphs	251	(24)
Ramsey's original theorems	252	(3)
Ramsey numbers	255	(3)
Induced Ramsey theorems	258	(10)
Ramsey properties and connectivity	268	(7)
Exercises	271	(1)
Notes	272	(3)
Hamilton Cycles	275	(18)
Simple sufficient conditions	275	(3)
Hamilton cycles and degree sequences	278	(3)
Hamilton cycles in the square of a graph	281	(12)
Exercises	289	(1)
Notes	290	(3)
Random Graphs	293	(22)
The notion of a random graph	294	(5)
The probabilistic method	299	(3)
Properties of almost all graphs	302	(4)
Threshold functions and second moments	306	(9)
Exercises	312	(1)
Notes	313	(2)
Minors, Trees and WQO	315	(42)
Well-quasi-ordering	316	(1)
The graph minor theorem for trees	317	(2)
Tree-decompositions	319	(8)
Tree-width and forbidden minors	327	(14)
The graph minor theorem	341	(16)
Exercises	350	(4)
Notes	354	(3)
Infinite sets	357	(4)
Surfaces	361	(8)
Hints for all the exercises	369	(24)
Index	393	(16)
Symbol index	409