## SEE: Guide to Download NPTEL Video Lecture

## Lecture Details :

Graph Theory by Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore. For more details on NPTEL visit http://nptel.iitm.ac.in

## Course Description :

Contents:

Introduction:Vertex cover and independent set - Matchings: Konig's theorem and Hall's theorem - More on Hall's theorem and some applications - Tutte's theorem on existence of a perfect matching - More on Tutte's theorem - More on Matchings - Dominating set, path cover - Gallai -- Millgram theorem, Dilworth's theorem - Connectivity: 2-connected and 3- connected graphs-Menger's theorem - More on connectivity: k- linkedness - Minors, topological minors and more on k- linkedness-Vertex coloring: Brooks theorem - More on vertex coloring - Edge coloring: Vizing's theorem - proof of Vizing's theorem, Introduction to planarity - coloring planar graphs, Kuratowsky's theorem-Proof of Kuratowsky's theorem, List coloring

List chromatic index - Adjacency polynomial of a graph and combinatorial Nullstellensatz - Chromatic polynomial, k - critical graphs - Gallai-Roy theorem, Acyclic coloring, Hadwiger's conjecture - Perfect graphs: Examples - interval graphs, chordal graphs - Proof of weak perfect graph theorem (WPGT) - Second proof of WPGT, Some non-perfect graph classes-More special classes of graphs - Boxicity,Sphericity, Hamiltonian circuits - More on Hamiltonicity: Chvatal's theorem - Chvatal's theorem, toughness, Hamiltonicity and 4-color conjecture - Network flows: Max flow mincut theorem - More on network flows: Circulations - Circulations and tensions - More on circulations and tensions, flow number and Tutte's flow conjectures - Ran Probabilistic method: Markov's inequality, Ramsey number - Probabilistic method: Graphs of high girth and high chromatic number,Second moment method, Lovasz local lemma, Graph minors and Hadwiger's conjecture - More on graph minors, tree decompositions

## Other Resources :

### Syllabus | Citation |

These lecture videos are delivered by IISc Bangalore, under the NPTEL program, lot of nptel video courses are available for learning online.

## Other Computer Science Courses

- Computer Organization by IIT Madras
- CS 161 - Computer Science by Portland Community College
- Design and Analysis of Algorithms by IIT Bombay
- The Structure and Interpretation of Computer Programs,Spring 2011 by UC Berkeley
- Multicore Programming Primer by MIT
- Artificial Intelligence III by IIT Madras
- Software Engineering I by Other
- Developing Mobile Apps with Web Technologies by Stanford
- The Joy of Computing,Fall 2011 by UC Berkeley
- Digital Computer Organization by IIT Kharagpur

### » check out the complete list of Computer Science Video lectures