Extremal Graph Theory

The ever-expanding field of extremal graph theory encompasses an array of problem-solving methods, including applications to economics, computer science, and optimization theory. This volume presents a concise yet comprehensive treatment, featuring complete proofs for almost all of its results and numerous exercises. 1978 edtion.

Preface

vii

Basic Definitions

xiii

Connectivity

1

(49)

Elementary Properties

2

(5)

Menger's Theorem and its Consequences

7

(4)

The Structure of 2- and 3-Connected Graphs

11

(6)

Minimally k-Connected Graphs

17

(12)

Graphs with Given Maximal Local Connectivity

29

(16)

Exercises, Problems and Conjectures

45

(5)

Matching

50

(52)

Fundamental Matching Theorems

52

(7)

The Number of 1-Factors

59

(8)

f-Factors

67

(12)

Matching in Graphs with Restrictions on the Degrees

79

(11)

Coverings

90

(5)

Exercises, Problems and Conjectures

95

(7)

Cycles

102

(67)

Graphs with Large Minimal Degree and Large Girth

103

(7)

Vertex Disjoint Cycles

110

(9)

Edge Disjoint Cycles

119

(12)

The Circumference

131

(16)

Graphs with Cycles of Given Lengths

147

(14)

Exercises, Problems and Conjectures

161

(8)

The Diameter

169

(49)

Diameter, Maximal Degree and Size

170

(11)

Diameter and Connectivity

181

(13)

Graphs with Large Subgraphs of Small Diameter

194

(12)

Factors of Small Diameter

206

(7)

Exercises, Problems and Conjectures

213

(5)

Colourings

218

(74)

General Colouring Theorems

221

(13)

Critical k-Chromatic Graphs

234

(9)

Colouring Graphs on Surfaces

243

(11)

Sparse Graphs of Large Chromatic Number

254

(9)

Perfect Graphs

263

(7)

Ramsey Type Theorems

270

(10)

Exercises, Problems and Conjectures

280

(12)

Complete Subgraphs

292

(76)

The Number of Complete Subgraphs

293

(16)

Complete Subgraphs of r-Partite Graphs

309

(18)

The Structure of Graphs

327

(12)

The Structure of Extremal Graphs without Forbidden Subgraphs

339

(12)

Independent Complete Subgraphs

351

(8)

Exercises, Problems and Conjectures

359

(9)

Topological Subgraphs

368

(33)

Contractions

369

(9)

Topological Complete Subgraphs

378

(8)

Semi-Topological Subgraphs

386

(11)

Exercises, Problems and Conjectures

397

(4)

Complexity and Packing

401

(37)

The Complexity of Graph Properties

402

(9)

Monotone Properties

411

(7)

The Main Packing Theorem

418

(7)

Packing Graphs of Small Size

425

(4)

Applications of Packing Results to Complexity

429

(5)

Exercises, Problems and Conjectures

434

(4)

References

438

(43)

Index of Symbols

481

(4)

Index of Definitions

485

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Extremal Graph Theory

Summary

Table of Contents

Supplemental Materials