Integer flows and cycle covers of graphs

(1997) ISBN: 0-8247-9790-6

Cun-Quan `C. Q.' Zhang

Publisher: Marcel Dekker, Inc.

270 Madison Ave.

New York, NY 10016



Click here for remarks, corrections and updates.
 

Click here for the ERRATA of the book.


Please send suggestion and comments to C. Q. Zhang


 

Contents

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     



Back to C.-Q. Zhang's home page.
Please send suggestion and comments to C. Q. Zhang