Click here for remarks, corrections and updates.
Click here for the ERRATA of the book.
Preface v Integer Flows 1 Chapter 1 Introduction to Integer Flows 3 1.1 Definitions and Tutte's conjectures 3 1.2 Elementary properties of flows 5 1.3 Modular flows 9 1.4 Flows and face colorings 12 1.5 Exercises 21 Chapter 2 Basic Properties of Integer Flows 25 2.1 Product of flows 25 2.2 Group flows 27 2.3 Bounded orientations 28 2.4 Cycle covers 30 2.5 Orientable cycle double cover 33 2.6 Sum of flows 35 2.7 Flow polynomial 37 2.8 Minimal counterexamples 38 2.9 Exercises 45 Chapter 3 Nowhere-Zero 4-Flows 49 3.1 Cycle covers and 4-flows 50 3.2 Parity subgraph decompositions 51 3.3 Evenly spanning cycles 53 3.4 4-edge-connected graphs 58 3.5 Faithful cycle covers 59 3.6 Orientable cycle double covers 62 3.7 Snarks 63 3.8 Collapsible graphs 76 3.9 Beyond the 4-color theorem 81 3.10 Exercises 84 3.11 Open problems 90 Chapter 4 Nowhere-Zero 3-Flows 93 4.1 Modular 3-orientations 93 4.2 Orientable cycle double covers 95 4.3 Weak 3-flow conjecture 96 4.4 3-color theorems 98 4.5 Exercises 106 4.6 Open problems 107 Chapter 5 Nowhere-Zero $k$-Flows (k ³ 5) 109 5.1 5-color theorem 110 5.2 8-flow theorem 112 5.3 6-flow theorem 114 5.4 Structure of 6-flow 117 5.5 Exercises 119 5.6 Open problems 121 Cycle Covers 123 Chapter 6 Faithful Cycle Covers 125 6.1 Introduction 125 6.2 Minimal contra-pairs 127 6.3 Circuit chain 128 6.4 Petersen graph and faithful covers (I) 132 6.5 Petersen graph and faithful covers (II) 133 6.6 Admissible dipath 137 6.7 Planar graphs and faithful covers 140 6.8 Fractional faithful cover 144 6.9 Exercises 146 6.10 Open problems 150 Chapter 7 Cycle Double Covers 153 7.1 Double covers and graph embeddings 153 7.2 Minimal counterexamples 155 7.3 Cycle 2k-covers 159 7.4 Five cycle double covers 162 7.5 Small circuit double covers 168 7.6 Exercises 169 7.7 Open problems 171 Chapter 8 Shortest Cycle Covers 175 8.1 Postman tour and shortest cover 175 8.2 Shortest cover and 4-flow (I) 180 8.3 Shortest cover and 4-flow (II) 183 8.4 Shortest cover and 8-flow (I) 184 8.5 Shortest cover and 8-flow (II) 188 8.6 Shortest cover and 6-flow 190 8.7 Shortest cover and 5-flow 197 8.8 Shortest cover and double cover 200 8.9 NP-completeness 204 8.10 Exercises 208 8.11 Open problems 210 Related Topics 213 Chapter 9 Generalization and Unification 215 9.1 Circular double covers 215 9.2 Modular orientation 216 9.3 Fractional flows 220 9.4 Cycle space minors 221 9.5 Group connectivity 223 9.6 Exercises 228 9.7 Open problems 231 Chapter 10 Compatible Decompositions 233 10.1 Introduction 233 10.2 Minimal contra-pairs 237 10.3 Planar graphs 242 10.4 $K_5$-free graphs 243 10.5 Forbidden system reduction 248 10.6 Exercises 258 10.7 Open problems 261 Chapter 11 Related Topics 263 11.1 Unique edge-3-coloring 263 11.2 Depth of circuit cover 268 11.3 Removable circuits 270 11.4 Even circuit decomposition 275 11.5 Exercises 276 11.6 Open problems 279 Appendices 281 A Fundamental Theorems 283 A.1 Some basic theorems 283 A.2 Edge-disjoint spanning trees 286 A.3 Cover by perfect matchings 290 A.4 Excluding Petersen minor 293 A.5 Vertex splitting 296 A.6 Exercises 299 A.7 Open problems 300 B Hints for Exercises 303 C Notations and Terminology 337 Bibliography 353 Index 373