Advanced Graph Theory and Combinatorics

Table of contents

1. Cover
2. Dedication
3. Title
4. Copyright
5. Foreword
6. Introduction
7. 1 A First Encounter with Graphs
   1. 1.1. A few definitions
   2. 1.2. Paths and connected components
   3. 1.3. Eulerian graphs
   4. 1.4. Defining Hamiltonian graphs
   5. 1.5. Distance and shortest path
   6. 1.6. A few applications
   7. 1.7. Comments
   8. 1.8. Exercises
8. 2 A Glimpse at Complexity Theory
   1. 2.1. Some complexity classes
   2. 2.2. Polynomial reductions
   3. 2.3. More hard problems in graph theory
9. 3 Hamiltonian Graphs
   1. 3.1. A necessary condition
   2. 3.2. A theorem of Dirac
   3. 3.3. A theorem of Ore and the closure of a graph
   4. 3.4. Chvátal’s condition on degrees
   5. 3.5. Partition of Kn into Hamiltonian circuits
   6. 3.6. De Bruijn graphs and magic tricks
   7. 3.7. Exercises
10. 4 Topological Sort and Graph Traversals
    1. 4.1. Trees
    2. 4.2. Acyclic graphs
    3. 4.3. Exercises
11. 5 Building New Graphs from Old Ones
    1. 5.1. Some natural transformations
    2. 5.2. Products
    3. 5.3. Quotients
    4. 5.4. Counting spanning trees
    5. 5.5. Unraveling
    6. 5.6. Exercises
12. 6 Planar Graphs
    1. 6.1. Formal definitions
    2. 6.2. Euler’s formula
    3. 6.3. Steinitz’ theorem
    4. 6.4. About the four-color theorem
    5. 6.5. The five-color theorem
    6. 6.6. From Kuratowski’s theorem to minors
    7. 6.7. Exercises
13. 7 Colorings
    1. 7.1. Homomorphisms of graphs
    2. 7.2. A digression: isomorphisms and labeled vertices
    3. 7.3. Link with colorings
    4. 7.4. Chromatic number and chromatic polynomial
    5. 7.5. Ramsey numbers
    6. 7.6. Exercises
14. 8 Algebraic Graph Theory
    1. 8.1. Prerequisites
    2. 8.2. Adjacency matrix
    3. 8.3. Playing with linear recurrences
    4. 8.4. Interpretation of the coefficients
    5. 8.5. A theorem of Hoffman
    6. 8.6. Counting directed spanning trees
    7. 8.7. Comments
    8. 8.8. Exercises
15. 9 Perron–Frobenius Theory
    1. 9.1. Primitive graphs and Perron’s theorem
    2. 9.2. Irreducible graphs
    3. 9.3. Applications
    4. 9.4. Asymptotic properties
    5. 9.5. The case of polynomial growth
    6. 9.6. Exercises
16. 10 Google’s Page Rank
    1. 10.1. Defining the Google matrix
    2. 10.2. Harvesting the primitivity of the Google matrix
    3. 10.3. Computation
    4. 10.4. Probabilistic interpretation
    5. 10.5. Dependence on the parameter α
    6. 10.6. Comments
17. Bibliography
18. Index
19. End User Licence Agreement