Bipartite graphs are perhaps the most basic of objects in graph theory, both from a theoretical and practical point of view. Until now, they have been considered only as a special class in some wider context. This work deals solely with bipartite graphs, providing traditional material as well as many new and unusual results. The authors illustrate the theory with many applications, especially to problems in timetabling, chemistry, communication networks and computer science. The material is accessible to any reader with a graduate understanding of mathematics and will be of interest to specialists in combinatorics and graph theory.
Author(s): Armen S. Asratian, Tristan M. J. Denley, Roland Häggkvist
Series: Cambridge Tracts in Mathematics
Publisher: Cambridge University Press
Year: 1998
Language: English
Pages: 271
Contents......Page 5
Preface......Page 7
Notation......Page 11
1.1 Graphs......Page 13
1.3 Reducibility of problems and NP-completeness......Page 16
2.1 Recognising bipartite graphs......Page 19
2.2 Bipartite graphs of certain types......Page 22
2.3 Matrix characterisations of bipartite graphs......Page 27
2.4 Gaussian elimination......Page 32
3.1 Radius and diameter......Page 35
3.2 Metric properties of trees......Page 40
3.3 Metric properties of the n-cube......Page 44
3.4 Addressing schemes for computer networks......Page 51
4.1 k-connected graphs......Page 57
4.2 k-edge-connected graphs......Page 60
4.3 The construction of linear superconcentrators......Page 64
5.1 Properties of maximum matchings......Page 68
5.2 Finding a maximum matching......Page 71
5.3 Maximum matchings in convex bipartite graphs......Page 77
5.4 Stable matchings......Page 79
5.5 The Generalised Assignment Problem......Page 83
6.1 Graphs with Hall's condition......Page 87
6.2 Expanding graphs......Page 94
6.3 Expanders......Page 97
6.4 Expanders and sorters......Page 102
7.1 (g,f)-factors......Page 109
7.2 Subgraphs with given degrees......Page 112
7.3 2-factors and Hamilton cycles......Page 118
7.4 T-joins......Page 126
7.5 Isomer problems in chemistry......Page 130
8.1 Edge colourings and timetables......Page 137
8.2 Interval edge colourings......Page 142
8.3 List colourings......Page 150
8.4 Colour-feasible sequences......Page 156
8.5 Transformations of proper colourings......Page 162
8.6 Uniquely colourable bipartite graphs......Page 168
8.7 Rearrangeable telephone networks......Page 172
9.1 Convex representations of doubly stochastic matrices......Page 175
9.2 Matrices with a unique convex representation......Page 178
9.3 Permanents and perfect matchings......Page 180
10.1 Some examples of covering problems......Page 186
10.2 Vertex coverings and independent sets......Page 191
10.3 Dulmage and Mendelsohn's canonical decomposition......Page 196
10.4 Decomposition of partially ordered sets into chains......Page 202
11.1 Systems of distinct representatives......Page 204
11.2 Generation of subsets of a set......Page 210
11.3 Pebbling in hypergrids......Page 213
11.4 Completing latin squares......Page 217
12.1 Spanning bipartite subgraphs......Page 226
12.2 Covering the edges of a graph with bipartite subgraphs......Page 230
12.3 Optimal spanning trees and the Travelling Salesman Problem......Page 238
12.4 The optimal spanning tree and optimal path problems......Page 241
Appendix......Page 244
References......Page 249
Index......Page 268
