Computer - Graph Theory (English)

   Monday, March 10, 2025   

Starting a new Lecture Notes Series on Computer - Graph Theory

Youtube Lecture Playlist Credits 

Channel Name: nptelhrd

So Let Us Start to This Journey of Learning 

Computer - Graph Theory By Lecture Notes together!

Lecture 1: Mod-01 Lec-01 Introduction: Vertex cover and independent set

Lecture 2: Mod-01 Lec-02 Matchings: Konig's theorem and Hall's theorem

Lecture 3: Mod-01 Lec-03 More on Hall's theorem and some applications

Lecture 4: Mod-01 Lec-04 Tutte's theorem on existence of a perfect matching

Lecture 5: Mod-01 Lec-05 More on Tutte's theorem

Lecture 6: Mod-01 Lec-06 More on Matchings

Lecture 7: Mod-01 Lec-07 Dominating set, path cover

Lecture 8: Mod-01 Lec-08 Gallai -- Millgram theorem, Dilworth's theorem

Lecture 9: Mod-02 Lec-09 Connectivity: 2-connected and 3- connected graphs

Lecture 10: Mod-02 Lec-10 Menger's theorem

Lecture 11: Mod-02 Lec-11 More on connectivity: k- linkedness

Lecture 12: Mod-02 Lec-12 Minors, topological minors and more on k- linkedness

Lecture 13: Mod-03 Lec-13 Vertex coloring: Brooks theorem

Lecture 14: Mod-03 Lec-14 More on vertex coloring

Lecture 15: Mod-03 Lec-15 Edge coloring: Vizing's theorem

Lecture 16: Mod-03 Lec-16 Proof of Vizing's theorem, Introduction to planarity

Lecture 17: Mod-03 Lec-17 5- coloring planar graphs, Kuratowsky's theorem

Lecture 18: Mod-03 Lec-18 Proof of Kuratowsky's theorem, List coloring

Lecture 19: Mod-03 Lec-19 List chromatic index

Lecture 20: Mod-03 Lec-20 Adjacency polynomial of a graph and combinatorial Nullstellensatz

Lecture 21: Mod-03 Lec-21 Chromatic polynomial, k - critical graphs

Lecture 22: Mod-03 Lec-22 Gallai-Roy theorem, Acyclic coloring, Hadwiger's conjecture

Lecture 23: Mod-04 Lec-23 Perfect graphs: Examples

Lecture 24: Mod-04 Lec-24 Interval graphs, chordal graphs

Lecture 25: Mod-04 Lec-25 Proof of weak perfect graph theorem (WPGT)

Lecture 26: Mod-04 Lec-26 Second proof of WPGT, Some non-perfect graph classes

Lecture 27: Mod-04 Lec-27 More special classes of graphs

Lecture 28: Mod-04 Lec-28 Boxicity,Sphericity, Hamiltonian circuits

Lecture 29: Mod-04 Lec-29 More on Hamiltonicity: Chvatal's theorem

Lecture 30: Mod-04 Lec-30 Chvatal's theorem, toughness, Hamiltonicity and 4-color conjecture

Lecture 31: Mod-05 Lec-31 Network flows: Max flow mincut theorem

Lecture 32: Mod-05 Lec-32 More on network flows: Circulations

Lecture 33: Mod-05 Lec-33 Circulations and tensions

Lecture 34: Mod-05 Lec-34 More on circulations and tensions, flow number and Tutte's flow conjectures

Lecture 35: Mod-06 Lec-35 Random graphs and probabilistic method: Preliminaries

Lecture 36: Mod-06 Lec-36 Probabilistic method: Markov's inequality, Ramsey number

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

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

Lecture 39: Mod-07 Lec-39 Graph minors and Hadwiger's conjecture

Lecture 40: Mod-07 Lec-40 More on graph minors, tree decompositions