## 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

- XML with,Java Servlet,and JSP by Harvard
- CSEP 524 Parallel Computation by University of Washington
- CSEP 590A History of Computing by University of Washington
- Introduction to Computer Science I by Harvard
- Digital Systems Design by IIT Kharagpur
- CSEP 501 Compiler Construction by University of Washington
- Internet Technologies by IIT Kharagpur
- Adobe Photoshop by Other
- Computer Language Engineering by MIT
- CSEP 590TU Practical Aspects of Modern Cryptography by University of Washington

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

### Get Your Degree!

Find schools and get information on the program that’s right for you.

Powered by Campus Explorer