Advanced Graph Theory and Combinatorics

Michel RIGO is Full Professor at the University of Liège, Department of Mathematics, in Belgium, where he is also head of the Discrete Mathematics research group. His current research interests include combinatorics on words, formal language theory and number theory.

• Foreword  ixIntroduction xiChapter 1. A First Encounter with Graphs  11.1. A few definitions  11.1.1. Directed graphs  11.1.2. Unoriented graphs 91.2. Paths and connected components  141.2.1. Connected components  161.2.2. Stronger notions of connectivity 181.3. Eulerian graphs  231.4. Defining Hamiltonian graphs 251.5. Distance and shortest path  271.6. A few applications 301.7. Comments 351.8. Exercises  37Chapter 2. A Glimpse at Complexity Theory 432.1. Some complexity classes 432.2. Polynomial reductions 462.3. More hard problems in graph theory 49Chapter 3. Hamiltonian Graphs 533.1. A necessary condition 533.2. A theorem of Dirac  553.3. A theorem of Ore and the closure of a graph  563.4. Chvátal’s condition on degrees  593.5. Partition of Kn into Hamiltonian circuits  623.6. De Bruijn graphs and magic tricks  653.7. Exercises  68Chapter 4. Topological Sort and Graph Traversals  694.1. Trees  694.2. Acyclic graphs 794.3. Exercises  82Chapter 5. Building New Graphs from Old Ones  855.1. Some natural transformations  855.2. Products  905.3. Quotients  925.4. Counting spanning trees  935.5. Unraveling 945.6. Exercises  96Chapter 6. Planar Graphs 996.1. Formal definitions 996.2. Euler’s formula 1046.3. Steinitz’ theorem  1096.4. About the four-color theorem 1136.5. The five-color theorem  1156.6. From Kuratowski’s theorem to minors  1206.7. Exercises  123Chapter 7. Colorings  1277.1. Homomorphisms of graphs  1277.2. A digression: isomorphisms and labeled vertices  1317.3. Link with colorings  1347.4. Chromatic number and chromatic polynomial 1367.5. Ramsey numbers  1407.6. Exercises  147Chapter 8. Algebraic Graph Theory  1518.1. Prerequisites  1518.2. Adjacency matrix 1548.3. Playing with linear recurrences  1608.4. Interpretation of the coefficients 1688.5. A theorem of Hoffman  1698.6. Counting directed spanning trees 1728.7. Comments 1778.8. Exercises  178Chapter 9. Perron–Frobenius Theory 1839.1. Primitive graphs and Perron’s theorem 1839.2. Irreducible graphs 1889.3. Applications  1909.4. Asymptotic properties 1959.4.1. Canonical form  1969.4.2. Graphs with primitive components 1979.4.3. Structure of connected graphs 2069.4.4. Period and the Perron–Frobenius theorem 2149.4.5. Concluding examples 2189.5. The case of polynomial growth  2249.6. Exercises  231Chapter 10. Google’s Page Rank  23310.1. Defining the Google matrix 23810.2. Harvesting the primitivity of the Google matrix  24110.3. Computation 24610.4. Probabilistic interpretation 24610.5. Dependence on the parameter α  24710.6. Comments 248Bibliography 249Index  263