Advanced Graph Theory and Combinatorics - Rigo, Michel

. .

Résumé :

Foreword? ix

Introduction xi

Chapter 1. A First Encounter with Graphs? 1

1.1. A few definitions? 1

1.1.1. Directed graphs? 1

1.1.2. Unoriented graphs 9

1.2. Paths and connected components? 14

1.2.1. Connected components? 16

1.2.2. Stronger notions of connectivity 18

1.3. Eulerian graphs? 23

1.4. Defining Hamiltonian graphs 25

1.5. Distance and shortest path? 27

1.6. A few applications 30

1.7. Comments 35

1.8. Exercises? 37

Chapter 2. A Glimpse at Complexity Theory 43

2.1. Some complexity classes 43

2.2. Polynomial reductions 46

2.3. More hard problems in graph theory 49

Chapter 3. Hamiltonian Graphs 53

3.1. A necessary condition 53

3.2. A theorem of Dirac? 55

3.3. A theorem of Ore and the closure of a graph? 56

3.4. Chv?tal's condition on degrees? 59

3.5. Partition of Kn into Hamiltonian circuits? 62

3.6. De Bruijn graphs and magic tricks? 65

3.7. Exercises? 68

Chapter 4. Topological Sort and Graph Traversals? 69

4.1. Trees? 69

4.2. Acyclic graphs 79

4.3. Exercises? 82

Chapter 5. Building New Graphs from Old Ones? 85

5.1. Some natural transformations? 85

5.2. Products? 90

5.3. Quotients? 92

5.4. Counting spanning trees? 93

5.5. Unraveling 94

5.6. Exercises? 96

Chapter 6. Planar Graphs 99

6.1. Formal definitions 99

6.2. Euler's formula 104

6.3. Steinitz' theorem? 109

6.4. About the four-color theorem 113

6.5. The five-color theorem? 115

6.6. From Kuratowski's theorem to minors? 120

6.7. Exercises? 123

Chapter 7. Colorings? 127

7.1. Homomorphisms of graphs? 127

7.2. A digression: isomorphisms and labeled vertices? 131

7.3. Link with colorings? 134

7.4. Chromatic number and chromatic polynomial 136

7.5. Ramsey numbers? 140

7.6. Exercises? 147

Chapter 8. Algebraic Graph Theory? 151

8.1. Prerequisites? 151

8.2. Adjacency matrix 154

8.3. Playing with linear recurrences? 160

8.4. Interpretation of the coefficients 168

8.5. A theorem of Hoffman? 169

8.6. Counting directed spanning trees 172

8.7. Comments 177

8.8. Exercises? 178

Chapter 9. Perron-Frobenius Theory 183

9.1. Primitive graphs and Perron's theorem 183

9.2. Irreducible graphs 188

9.3. Applications? 190

9.4. Asymptotic properties 195

9.4.1. Canonical form? 196

9.4.2. Graphs with primitive components 197

9.4.3. Structure of connected graphs 206

9.4.4. Period and the Perron-Frobenius theorem 214

9.4.5. Concluding examples 218

9.5. The case of polynomial growth? 224

9.6. Exercises? 231

Chapter 10. Google's Page Rank? 233

10.1. Defining the Google matrix 238

10.2. Harvesting the primitivity of the Google matrix? 241

10.3. Computation 246

10.4. Probabilistic interpretation 246

10.5. Dependence on the parameter ?? 247

10.6. Comments 248

Bibliography 249

Index? 263