Bipartite Graphs and Their ApplicationsThis is the first book which deals solely with bipartite graphs. Together with traditional material, the reader will also find many new and unusual results. Essentially all proofs are given in full; many of these have been streamlined specifically for this text. Numerous exercises of all standards have also been included. The theory is illustrated with many applications especially to problems in timetabling, Chemistry, Communication Networks and Computer Science. For the most part the material is accessible to any reader with a graduate understanding of mathematics. However, the book contains advanced sections requiring much more specialized knowledge, which will be of interest to specialists in combinatorics and graph theory. |
Contents
Basic concepts | 1 |
Introduction to bipartite graphs | 7 |
Metric properties | 23 |
Connectivity | 45 |
Maximum matchings | 56 |
Expanding properties | 75 |
Subgraphs with restricted degrees | 97 |
Edge colourings | 125 |
Other editions - View all
Bipartite Graphs and their Applications Armen S. Asratian,Tristan M. J. Denley,Roland Häggkvist No preview available - 2008 |
Bipartite Graphs and Their Applications Armen S. Asratian,Tristan M. J. Denley,Roland Häggkvist No preview available - 1998 |
Common terms and phrases
adjacency matrix adjacent Asratian augmenting path augmenting path relative bipartite subgraph bisimplicial called cardinality colour classes colouring of G complete bipartite graph connected graph consider construct contains contradicts Corollary corresponding dc(x decomposition define degree deleting denote doubly stochastic matrix edge-disjoint edges incident edges joining edges of G eigenvalue elements exists G is bipartite G with bipartition graph G graph with bipartition Hamilton cycle Hamilton path induced subgraph input internally disjoint isomorphic Kn,n Konig's latin square least Lemma length Let G matching of G maximum matching minimum vertex covering n-cube NP-complete number of edges pair of vertices partition pebbles pendant vertices perfect matching permutation positive integer Proof proper t-colouring Property Proposition Prove regular bipartite graph result follows sequence set of vertices Show simple bipartite graph simple graph spanning tree stable matching subgraph H subgraph of G symbol timetable triangle-free graph uniquely edge colourable vertex set
Popular passages
Page 240 - Some upper bounds on the total and list chromatic numbers of multigraphs, J. Graph Theory 16 (1992), 503-516.