Introduction to graph theory = 图论导引 / 2nd ed.

contents

preface

chapter 1 fundamental concepts

1.1 what is a graph?

the definition, 1

graphs as models, 3

matrices and isomorphism, 6

. decomposition and special graphs, 11

exercises, 14

1.2 paths, cycles, and trails

connection in graphs, 20

bipartite graphs, 24

eulerian circuits, 26

exercises, 31

1.3 vertex degrees and counting

counting and bijections, 35

extremal problems, 38

graphic sequences, 44

exercises, 47

1.4 directed graphs

.definitions and examples, 53

vertex degrees, 58

eulerian digraphs, 60

orientations and tournaments, 61

exercises, 63

chapter 2 trees and distance

2.1 basic properties

properties of trees, 68

distance in trees and graphs, 70

disjoint spanning trees (optional), 73

exercises, 75

2.2 spanning trees and enumeration

enumeration of trees, 81

spanning trees in graphs, 83

decomposition and graceful labelings, 87

branchings and eulerian digraphs (optional), 89

exercises, 92

2.3 optimization and trees

minimum spanning tree, 95

shortest paths, 97

trees in computer science (optional), 100

exercises, 103

chapter 3 matchings and factors

3.1 matchings and covers

maximum matchings, 108

hall's matching condition, 110

mm-max theorems, 112

independent sets and covers, 113

dominating sets (optional), 116

exercises, 118

3.2 algorithms and applications

maximum bipartite matching, 123

weighted bipartite matching, 125

stable matchings (optional), 130

faster bipartite matching (optional), 132

exercises, 134

3.3 matchings in general graphs

tutte's l-factor theorem, 136

f-factors of graphs (optional), 140

edmonds' blossom algorithm (optional), 142

exercises, 145

chapter 4 connectivity and paths

4.1 cuts and connectivity

connectivity, 149

edge-connectivity, 152

blocks, 155

exercises, 158

4.2 k-connected graphs

2-connected graphs, 161

connectivity of digraphs, 164

k-connected and k-edge-connected graphs, 166

applications of menger's theorem, 170

exercises, 172

4.3 network flow problems

maximum network flow, 176

integral flows 181

supplies and demands (optional), 184

exercises, 188

chapter 5 coloring of graphs

5.1 vertex colorings and upper bounds

definitions and examples, 191

upper bounds, 194

brooks' theorem, 197

exercises, 199

5.2 structure of k-chromatic graphs

graphs with large chromatic number, 205

extremal problems and turan's theorem 207

color-critical graphs, 210

forced subdivisions, 212

exercises, 214

5.3 enumerative aspects

counting proper colorings, 219

chordal graphs, 224

a hint of perfect graphs, 226

counting acyclic orientations (optional), 228

exercises, 229

chapter 6 planar graphs

6.1 embeddings and euler's formula

drawings in the plane, 233

dual graphs, 236

euler's formula, 241 255

exercises, 243

6.2 characterization of planar graphs

preparation for kuratowski's theorem, 247

convex embeddings, 248

planarity testing (optional), 252

exercises, 255

6.3 parameters of planarity

coloring of planar graphs, 257

crossing number, 261

surfaces of higher genus (optional), 266

exercises, 269

chapter 7 edges and cycles

7.1 line graphs and edge-coloring

edge-colorings, 274

characterization of line graphs (optional), 279

exercises, 282

7.2 hamiltonian cycles

necessary conditions, 287

sufficient conditions, 288

cycles in directed graphs (optional), 293

exercises, 294

7.3 planarity, coloring, and cycles

tait's theorem, 300

grinberg's theorem, 302

snarks (optional), 304

flows and cycle covers (optional), 307

exercises, 314

chapter 8 additional topics (optional)

8.1 perfect graphs

the perfect graph theorem, 320

chordal graphs revisited, 323

other classes of perfect graphs, 328

imperfect graphs, 334

the strong perfect graph conjecture, 340

exercises, 344

8.2 matroids

hereditary systems and examples, 349

properties of matroids, 354

the span function, 358

the dual of a matroid, 360

matroid minors and planar graphs, 363

matroid intersection, 366

matroid union, 369

exercises, 372

8.3 pamsey theory,

the pigeonhole principle revisited, 378

ramsey's theorem, 380

ramsey numbers, 383

'graph ramsey theory, 386

sperner's lemma and bandwidth, 388

exercises, 392

8.4 more extremal problems

encodings of graphs, 397

branchings and gossip, 404

list coloring and choosability, 408

partitions using paths and cycles, 413

circumference, 416

exercises, 422

8.5 random graphs

existence and expectation, 426

properties of almost all graphs, 430

threshold functions, 432

evolution and graph parameters, 436

connectivity, cliques, and coloring, 439

martingales, 442

exercises, 448

8.6 eigenvalues of graphs

the characteristic polynomial, 453

linear algebra of real symmetric matrices, 456

eigenvalues and graph parameters, 458

eigenvalues of regular graphs, 460

eigenvalues and expanders, 463

strongly regular graphs, 464

exercises, 467

appendix a mathematical background

sets, 471

quantifiers and proofs, 475

induction and recurrence, 479

functions, 483

counting and binomial coefficients, 485

relations, 489

the pigeonhole principle, 491

appendix b optimization and complexity

intractability, 493

heuristics and bounds, 496

np-completeness proofs, 499

exercises, 505

appendix c hints for selected exercises

general discussion, 507

supplemental specific hints, 508

appendix d glossary of terms

appendix e supplemental reading

appendix f references

author index

subject index