Graph Theory


Lecture 1 - Introduction: Vertex cover and independent set


Lecture 2 - Matchings: Konig’s theorem and Hall’s theorem


Lecture 3 - More on Hall’s theorem and some applications


Lecture 4 - Tutte’s theorem on existence of a perfect matching


Lecture 5 - More on Tutte’s theorem


Lecture 6 - More on Matchings


Lecture 7 - Dominating set, path cover


Lecture 8 - Gallai – Millgram theorem, Dilworth’s theorem


Lecture 9 - Connectivity: 2-connected and 3-connected graphs


Lecture 10 - Menger’s theorem


Lecture 11 - More on connectivity: k- linkedness


Lecture 12 - Minors, topological minors and more on k- linkedness


Lecture 13 - Vertex coloring: Brooks theorem


Lecture 14 - More on vertex coloring


Lecture 15 - Edge coloring: Vizing’s theorem


Lecture 16 - Proof of Vizing’s theorem, Introduction to planarity


Lecture 17 - 5- coloring planar graphs, Kuratowsky’s theorem


Lecture 18 - Proof of Kuratowsky’s theorem, List coloring


Lecture 19 - List chromatic index


Lecture 20 - Adjacency polynomial of a graph and combinatorial Nullstellensatz


Lecture 21 - Chromatic polynomial, k - critical graphs


Lecture 22 - Gallai-Roy theorem, Acyclic coloring, Hadwiger’s conjecture


Lecture 23 - Perfect graphs: Examples


Lecture 24 - Interval graphs, chordal graphs


Lecture 25 - Proof of weak perfect graph theorem (WPGT)


Lecture 26 - Second proof of WPGT, Some non-perfect graph classes


Lecture 27 - More special classes of graphs


Lecture 28 - Boxicity,Sphericity, Hamiltonian circuits


Lecture 29 - More on Hamiltonicity: Chvatal’s theorem


Lecture 30 - Chvatal’s theorem, toughness, Hamiltonicity and 4-color conjecture


Lecture 31 - Network flows: Max flow mincut theorem


Lecture 32 - More on network flows: Circulations


Lecture 33 - Circulations and tensions


Lecture 34 - More on circulations and tensions, flow number and Tutte’s flow conjectures


Lecture 35 - Random graphs and probabilistic method: Preliminaries


Lecture 36 - Probabilistic method: Markov’s inequality, Ramsey number


Lecture 37 - Probabilistic method: Graphs of high girth and high chromatic number


Lecture 38 - Probabilistic method: Second moment method, Lovasz local lemma


Lecture 39 - Graph minors and Hadwiger’s conjecture


Lecture 40 - More on graph minors, tree decompositions