Graph Theory by L. Sunil Chandran (IISc Bangalore)

# click the upper-left icon to select videos from the playlist
source: nptelhrd     2012年5月21日
Computer - 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

01 Introduction: Vertex cover and independent set 56:13
02 Matchings: Konig's theorem and Hall's theorem 58:27
03 More on Hall's theorem and some applications 57:38
04 Tutte's theorem on existence of a perfect matching 58:07
05 More on Tutte's theorem 58:10
06 More on Matchings 57:58
07 Dominating set, path cover 58:45
08 Gallai -- Millgram theorem, Dilworth's theorem 57:51
09 Connectivity: 2-connected and 3- connected graphs 58:03
10 Menger's theorem 56:17
11 More on connectivity: k- linkedness 55:28
12 Minors, topological minors and more on k- linkedness 55:33
13 Vertex coloring: Brooks theorem 57:21
14 More on vertex coloring 55:34
15 Edge coloring: Vizing's theorem 56:36
16 Proof of Vizing's theorem, Introduction to planarity 56:52
17 5- coloring planar graphs, Kuratowsky's theorem 57:32
18 Proof of Kuratowsky's theorem, List coloring 56:48
19 List chromatic index 57:37
20 Adjacency polynomial of a graph and combinatorial Nullstellensatz 56:30
21 Chromatic polynomial, k - critical graphs 57:07
22 Gallai-Roy theorem, Acyclic coloring, Hadwiger's conjecture 54:03
23 Perfect graphs: Examples 57:24
24 Interval graphs, chordal graphs 57:08
25 Proof of weak perfect graph theorem (WPGT) 56:35
26 Second proof of WPGT, Some non-perfect graph classes 57:48
27 More special classes of graphs 57:38
28 Boxicity,Sphericity, Hamiltonian circuits 57:02
29 More on Hamiltonicity: Chvatal's theorem 57:36
30 Chvatal's theorem, toughness, Hamiltonicity and 4-color conjecture 59:00
31 Network flows: Max flow mincut theorem 57:52
32 More on network flows: Circulations 58:35
33 Circulations and tensions 58:20
34 More on circulations and tensions, flow number and Tutte's flow conjectures 56:50
35 Random graphs and probabilistic method: Preliminaries 57:25
36 Probabilistic method: Markov's inequality, Ramsey number 57:34
37 Probabilistic method: Graphs of high girth and high chromatic number 58:20
38 Probabilistic method: Second moment method, Lovasz local lemma 58:50
39 Graph minors and Hadwiger's conjecture 58:28
40 More on graph minors, tree decompositions 58:31