Course

Graph Theory

Indian Institute of Science Bangalore

In computer science, graph theory is used extensively. The intension of this course is to introduce the subject of graph theory to computer science students in a thorough way. While the course will cover all elementary concepts such as coloring, covering, hamiltonicity, planarity, connectivity and so on, it will also introduce the students to some advanced concepts.

Course topics:

Vertex Cover
Matchings
Pathcover
Connectivity
Hamiltonicity
Vertex Coloring
Edge Coloring
Other Coloring Problems
Perfect graphs
Planar graphs
Other special classes of graphs
Network flow
Introduction to minor theory
Probabilistic Methods: Basics
Markov, Chebishey Inequalities
Lovasz Local Lemma
Random graph

Course Lectures

Mod-01 Lec-01 Introduction: Vertex cover and independent set
Dr. L. Sunil Chandran

Play
Mod-01 Lec-02 Matchings: Konig's theorem and Hall's theorem
Dr. L. Sunil Chandran

Play
Mod-01 Lec-03 More on Hall's theorem and some applications
Dr. L. Sunil Chandran

Play
Mod-01 Lec-04 Tutte's theorem on existence of a perfect matching
Dr. L. Sunil Chandran

Play
Mod-01 Lec-05 More on Tutte's theorem
Dr. L. Sunil Chandran

Play
Mod-01 Lec-06 More on Matchings
Dr. L. Sunil Chandran

Play
Mod-01 Lec-07 Dominating set, path cover
Dr. L. Sunil Chandran

Play
Mod-01 Lec-08 Gallai -- Millgram theorem, Dilworth's theorem
Dr. L. Sunil Chandran

Play
Mod-02 Lec-09 Connectivity: 2-connected and 3- connected graphs
Dr. L. Sunil Chandran

Play
Mod-02 Lec-10 Menger's theorem
Dr. L. Sunil Chandran

Play
Mod-02 Lec-11 More on connectivity: k- linkedness
Dr. L. Sunil Chandran

Play
Mod-02 Lec-12 Minors, topological minors and more on k- linkedness
Dr. L. Sunil Chandran

Play
Mod-03 Lec-13 Vertex coloring: Brooks theorem
Dr. L. Sunil Chandran

Play
Mod-03 Lec-14 More on vertex coloring
Dr. L. Sunil Chandran

Play
Mod-03 Lec-15 Edge coloring: Vizing's theorem
Dr. L. Sunil Chandran

Play
Mod-03 Lec-16 Proof of Vizing's theorem, Introduction to planarity
Dr. L. Sunil Chandran

Play
Mod-03 Lec-17 5- coloring planar graphs, Kuratowsky's theorem
Dr. L. Sunil Chandran

Play
Mod-03 Lec-18 Proof of Kuratowsky's theorem, List coloring
Dr. L. Sunil Chandran

Play
Mod-03 Lec-19 List chromatic index
Dr. L. Sunil Chandran

Play
Mod-03 Lec-20 Adjacency polynomial of a graph and combinatorial Nullstellensatz
Dr. L. Sunil Chandran

Play
Mod-03 Lec-21 Chromatic polynomial, k - critical graphs
Dr. L. Sunil Chandran

Play
Mod-03 Lec-22 Gallai-Roy theorem, Acyclic coloring, Hadwiger's conjecture
Dr. L. Sunil Chandran

Play
Mod-04 Lec-23 Perfect graphs: Examples
Dr. L. Sunil Chandran

Play
Mod-04 Lec-24 Interval graphs, chordal graphs
Dr. L. Sunil Chandran

Play
Mod-04 Lec-25 Proof of weak perfect graph theorem (WPGT)
Dr. L. Sunil Chandran

Play
Mod-04 Lec-26 Second proof of WPGT, Some non-perfect graph classes
Dr. L. Sunil Chandran

Play
Mod-04 Lec-27 More special classes of graphs
Dr. L. Sunil Chandran

Play
Mod-04 Lec-28 Boxicity,Sphericity, Hamiltonian circuits
Dr. L. Sunil Chandran

Play
Mod-04 Lec-29 More on Hamiltonicity: Chvatal's theorem
Dr. L. Sunil Chandran

Play
Mod-04 Lec-30 Chvatal's theorem, toughness, Hamiltonicity and 4-color conjecture
Dr. L. Sunil Chandran

Play
Mod-05 Lec-31 Network flows: Max flow mincut theorem
Dr. L. Sunil Chandran

Play
Mod-05 Lec-32 More on network flows: Circulations
Dr. L. Sunil Chandran

Play
Mod-05 Lec-33 Circulations and tensions
Dr. L. Sunil Chandran

Play
Mod-05 Lec-34 More on circulations and tensions, flow number and Tutte's flow conjectures
Dr. L. Sunil Chandran

Play
Mod-06 Lec-35 Random graphs and probabilistic method: Preliminaries
Dr. L. Sunil Chandran

Play
Mod-06 Lec-36 Probabilistic method: Markov's inequality, Ramsey number
Dr. L. Sunil Chandran

Play
Mod-06 Lec-37 Probabilistic method: Graphs of high girth and high chromatic number
Dr. L. Sunil Chandran

Play
Mod-06 Lec-38 Probabilistic method: Second moment method, Lovasz local lemma
Dr. L. Sunil Chandran

Play
Mod-07 Lec-39 Graph minors and Hadwiger's conjecture
Dr. L. Sunil Chandran

Play
Mod-07 Lec-40 More on graph minors, tree decompositions
Dr. L. Sunil Chandran

Play