106108054 Computer Science and Engineering Graph Theory Dr. L. Sunil Chandran Video IISc Bangalore
Select
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
5- 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
Random graphs and probabilistic method: Preliminaries
Probabilistic method: Markov�s inequality, Ramsey number
Probabilistic method: Graphs of high girth and high chromatic number
Probabilistic method: Second moment method, Lovasz local lemma
Graph minors and Hadwiger�s conjecture
More on graph minors, tree decompositions
Contributed and Presented by 
Proudly Hosted by 
