Graphs and hypergraphs

Graphs and Hypergraphs......Page 4
Copyright Page......Page 5
TABLE OF CONTENTS......Page 12
PART ONE GRAPHS......Page 16
1. Graphs......Page 18
2. Basic definitions......Page 20
3. List of symbols......Page 24
1. Cycles and cocycles......Page 27
2. Cycles in a planar graph......Page 32
1. Trees and cotrees......Page 39
2. Strongly connected graphs and graphs without circuits......Page 43
3. Arborescences......Page 47
4. Injective, functional and semi-functional graphs......Page 51
5. Counting trees......Page 57
1. The path problem......Page 70
2. The shortest path problem......Page 74
3. Centres and radii of a quasi-strongly connected graph......Page 76
4. Diameter of a strongly connected graph......Page 81
5. Counting paths......Page 89
1. The maximum flow problem......Page 91
2. The compatible flow problem......Page 101
3. An algebraic study of flows and tensions......Page 104
4. The maximum tension problem......Page 110
1. Existence of a p-graph with given demi-degrees......Page 117
2. Existence of a p-graph without loops with given demi-degrees......Page 124
3. Existence of a simple graph with given degrees......Page 130
1. The maximum matching problem......Page 137
2. The minimum covering problem......Page 144
3. Matchings in bipartite graphs......Page 146
4. An extension of the König theorem......Page 156
5. Counting perfect matchings......Page 157
1. The maximum c-matching problem......Page 165
2. Transfers......Page 168
3. Maximum cardinality of a c-matching......Page 170
1. h-Connected graphs......Page 179
2. Articulation vertices and blocks......Page 190
3. k-Edge-connected graphs......Page 196
1. Hamiltonian paths and circuits......Page 201
2. Hamiltonian paths in complete graphs......Page 207
3. Existence theorems for hamiltonian circuits......Page 210
4. Existence theorems for hamiltonian cycles......Page 219
5. Hamilton-connected graphs......Page 232
6. Hamiltonian cycles in planar graphs (abstract)......Page 238
1. Eulerian cycles......Page 243
2. Covering edges with disjoint chains......Page 247
3. Counting eulerian circuits......Page 254
1. Edge colourings......Page 263
2. The Vizing theorem and related results......Page 269
3. Edge colourings of planar graphs (abstract)......Page 282
1. Maximum stable sets......Page 287
2. The Turán theorem and related results......Page 293
3. alpha-Critical graphs......Page 300
4. Critical vertices and critical edges......Page 312
5. Stability number and vertex coverings by paths......Page 313
1. Absorption number......Page 318
2. Kernels......Page 322
3. Grundy functions......Page 327
4. Nim games......Page 333
1. Vertex colourings......Page 340
2. gamma-Critical graphs......Page 353
3. The Hajós theorem......Page 365
4. Chromatic polynomials......Page 367
5. Vertex colourings of planar graphs (abstract)......Page 370
1. Perfect graphs......Page 375
2. Comparability graphs......Page 378
3. Triangulated graphs......Page 383
4. i-Triangulated graphs......Page 384
5. Interval graphs......Page 386
6. Cartesian product and Cartesian sum of simple graphs......Page 391
PART TWO HYPERGRAPHS......Page 402
1. Hypergraphs......Page 404
2. Cycles in a hypergraph......Page 406
3. Conformal hypergraphs......Page 411
4. Representative graph of a hypergraph......Page 415
1. Matchings and c-matchings......Page 429
2. Transversal number......Page 435
1. Stability number and chromatic number of a hypergraph......Page 444
2. Cliques of a hypergraph......Page 448
3. Good colourings of the edges of a graph......Page 456
4. Generalizations of the chromatic number of a graph......Page 459
1. Strong chromatic number......Page 464
2. Balanced hypergraphs......Page 466
3. Unimodular hypergraphs......Page 479
4. Stochastic functions......Page 485
1. Matroid on a set......Page 492
2. The Rado theorem and related results......Page 497
3. Image of a matroid......Page 502
4. Minimum weight basis......Page 509
REFERENCES......Page 514
INDEX OF DEFINITIONS......Page 539