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

Course Curriculum

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

This Course is provided by IISc Bangalore as part of NPTEL online courses.

Course Reviews

N.A

ratings
  • 5 stars0
  • 4 stars0
  • 3 stars0
  • 2 stars0
  • 1 stars0

No Reviews found for this course.

About

FreeVideoLectures Provides you complete information about best courses online, Video tutorials, helps you in building a career !!

help@freevideolectures.com

Learn More About us

About Us
Privacy Policy
FAQ

FREEVIDEOLECTURES.COM ALL RIGHTS RESERVED.
top
FreeVideoLectures.com All rights reserved.

Setup Menus in Admin Panel