Home »Computer Science »IISc Bangalore » Graph Theory



Graph Theory

IISc Bangalore Course , Prof. L. Sunil Chandran       Subscribe to feed

Lights off      

Lecture 36: Mod-06 Lec-36 Probabilistic method: Markov's inequality, Ramsey number

Embed
Download:   MP4, FLV and 3GP 447 views

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 :

In computer science, graph theory is used extensively. The intension of this course is to introduce the subject of graph theory to computer science students in a thorough way.
While the course will cover all elementary concepts such as coloring, covering, hamiltonicity, planarity, connectivity and so on, it will also introduce the students to some advanced concepts.

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

» check out the complete list of Computer Science Video lectures          

 

Computer Science Lecture Notes

 

Comments

Post your Comments

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