Advanced Graph Theory and Combinatorics

Introduction

This book is a result of lecture notes from a graph theory course taught at the University of Liège since 2005. Through the years, this course evolved and lectures were given at different levels ranging from second-year undergraduates in mathematics to students in computer science entering master’s studies. It was therefore quite challenging to find a suitable title for this book.

Advanced or not so advanced material?

I hope that the reader will not feel cheated by the title (which is always tricky to choose). In some aspects, the material is rather elementary: we will start from scratch and present basic results on graphs such as connectedness or Eulerian graphs. In the second part of the book, we will analyze in great detail the strongly connected components of a digraph and make use of Perron–Frobenius theory and formal power series to estimate asymptotics on the number of walks of a given length between two vertices. Topics with an algebraic or a combinatorial flavor such as Ramsey numbers, introduction to Robertson–Seymour theorem or PageRank can be considered as more advanced.

In the history of mathematics, we often mention the seven bridges of Königsberg problem as the very first problem in graph theory. It was studied by the famous mathematician L. Euler in 1736. It took two centuries to develop and build a complete theory from a few scattered results. Probably the first book on graphs is Theorie der endlichen und unendlichen Graphen [KÖN 90] written by the ...