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

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 Mathematics Courses

- Linear programming and Extensions by IIT Kanpur
- Differential equations III by Other
- Elementary Numerical Analysis by IIT Bombay
- A Basic Course in Real Analysis by IIT Kharagpur
- Pre-algebra by Khan Academy
- Introduction to Geometry by Other
- AMC Function by Other
- Linear Algebra - Khan Academy by Khan Academy
- Math 3C: Probability for Math Science by UCLA
- Topology by IIT Madras

### » check out the complete list of Mathematics Video lectures