Learn · NPTEL

Course10610805440 lectures

Graph Theory

Dr. L. Sunil Chandran · IISc Bangalore

Start with lecture 1 At NPTEL

Lectures

Covering problems

  1. Introduction: Vertex cover and independent set Video
  2. Matchings: Konigs theorem and Halls theorem Video
  3. More on Halls theorem and some applications Video
  4. Tuttes theorem on existence of a perfect matching Video
  5. More on Tuttes theorem Video
  6. More on Matchings Video
  7. Dominating set, path cover Video
  8. Gallai : Millgram theorem, Dilworths theorem Video

Connectivity

  1. Connectivity: 2-connected and 3- connected graphs Video
  2. Mengers theorem Video
  3. More on connectivity: k- linkedness Video
  4. Minors, topological minors and more on k- linkedness Video

Coloring

  1. Vertex coloring: Brooks theorem Video
  2. More on vertex coloring Video
  3. Edge coloring: Vizings theorem Video
  4. Proof of Vizings theorem, Introduction to planarity Video
  5. 5- coloring planar graphs, Kuratowskys theorem Video
  6. Proof of Kuratowskys theorem, List coloring Video
  7. List chromatic index Video
  8. Adjacency polynomial of a graph and combinatorial Nullstellensatz Video
  9. Chromatic polynomial, k - critical graphs Video
  10. Gallai-Roy theorem, Acyclic coloring, Hadwigers conjecture Video

Special classes of graphs

  1. Perfect graphs: Examples Video
  2. Interval graphs, chordal graphs Video
  3. Proof of weak perfect graph theorem (WPGT) Video
  4. Second proof of WPGT, Some non-perfect graph classes Video
  5. More special classes of graphs Video
  6. Boxicity,Sphericity, Hamiltonian circuits Video
  7. More on Hamiltonicity: Chvatals theorem Video
  8. Chvatals theorem, toughness, Hamiltonicity and 4-color conjecture Video

Network flows

  1. Network flows: Max flow mincut theorem Video
  2. More on network flows: Circulations Video
  3. Circulations and tensions Video
  4. More on circulations and tensions, flow number and Tuttes flow conjectures Video

Random graphs and probabilistic method

  1. Random graphs and probabilistic method: Preliminaries Video
  2. Probabilistic method: Markovs inequality, Ramsey number Video
  3. Probabilistic method: Graphs of high girth and high chromatic number Video
  4. Probabilistic method: Second moment method, Lovasz local lemma Video

Graph minors

  1. Graph minors and Hadwigers conjecture Video
  2. More on graph minors, tree decompositions Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IISc Bangalore
Department
Computer Science and Engineering
Teacher
Dr. L. Sunil Chandran
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed