Graph theory
Enseignant responsable :
Volume horaire : 36Description du contenu de l'enseignement :
Volume horaire : CM : 18h TD : 18h
This class provides a presentation and study of some structures and graph problems which have important applications in practice.
We will start with basic notions (isomorphism, graph decomposition and special graphs), followed by paths, cycles, and trails, vertex degrees and counting (extremal problems, graphic sequences), directed graphs (orientations and tournaments). We will continue by studying matchings including Hall's theorem and the stable marriage theorem of Gale and Shapley. If time permits, we will also look at Tutte's theorem on perfect matchings. Next, we will look at connectedness and structure such as Menger's theorem. After this, we will consider planar graphs, looking at Kuratowski's characterization of planarity and Euler's formula. Finally, we will study in important notion in graph theory: graph coloring. We will look at Brooks' classical theorem, look at the Four Color Theorem and prove the 5-color theorem. Time permitting, at the end of the course we will look at Ramsey theory and/or the probabilistic method.