Graph Theory
Graph Theory. Instructor: Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore. In computer science, graph theory is used extensively. The aim 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. (from nptel.ac.in)
| Covering Problems |
| Lecture 01 - Introduction: Vertex Cover and Independent Set |
| Lecture 02 - Matchings: Konig's Theorem and Hall's Theorem |
| Lecture 03 - More on Hall's Theorem and Some Applications |
| Lecture 04 - Tutte's Theorem on Existence of a Perfect Matching |
| Lecture 05 - More on Tutte's Theorem |
| Lecture 06 - More on Matchings |
| Lecture 07 - Dominating Set, Path Cover |
| Lecture 08 - Gallai-Milgram Theorem, Dilworth's Theorem |
| Connectivity |
| Lecture 09 - Connectivity: 2-Connected and 3-Connected Graphs |
| Lecture 10 - Menger's Theorem |
| Lecture 11 - More on Connectivity: K-Linkedness |
| Lecture 12 - Minors, Topological Minors and More on K-Linkedness |
| Coloring |
| Lecture 13 - Vertex Coloring: Brooks' Theorem |
| Lecture 14 - More on Vertex Coloring |
| Lecture 15 - Edge Coloring: Vizing's Theorem |
| Lecture 16 - Proof of Vizing's Theorem, Introduction to Planarity |
| Lecture 17 - 5-Coloring Planar Graphs, Kuratowski's Theorem |
| Lecture 18 - Proof of Kuratowski's Theorem, List Coloring |
| Lecture 19 - List Chromatic Index |
| Lecture 20 - Adjacency Polynomial of a Graph and Combinatorial Nullstellensatz |
| Lecture 21 - Chromatic Polynomial, K-Critical Graphs |
| Lecture 22 - Gallai-Roy Theorem, Acyclic Coloring, Hadwiger Conjecture |
| Special Classes of Graphs |
| Lecture 23 - Perfect Graphs: Examples |
| Lecture 24 - Interval Graphs, Chordal Graphs |
| Lecture 25 - Proof of Weak Perfect Graph Theorem (WPGT) |
| Lecture 26 - Second Proof of WPGT, Some Non-perfect Graph Classes |
| Lecture 27 - More Special Classes of Graphs |
| Lecture 28 - Boxicity, Sphericity, Hamiltonian Circuits |
| Lecture 29 - More on Hamiltonicity: Chvatal's Theorem |
| Lecture 30 - Chvatal's Theorem, Toughness, Hamiltonicity and 4-Color Conjecture |
| Network Flows |
| Lecture 31 - Network Flows: Max-Flow Min-Cut Theorem |
| Lecture 32 - More on Network Flows: Circulations |
| Lecture 33 - Circulations and Tensions |
| Lecture 34 - More on Circulations and Tensions, Flow Number and Tutte's Flow Conjectures |
| Random Graphs and Probabilistic Method |
| Lecture 35 - Random Graphs and Probabilistic Method: Preliminaries |
| Lecture 36 - Probabilistic Method: Markov's Inequality, Ramsey Number |
| Lecture 37 - Probabilistic Method: Graphs of High Girth and High Chromatic Number |
| Lecture 38 - Probabilistic Method: Second Moment Method, Lovasz Local Lemma |
| Graph Minors |
| Lecture 39 - Graph Minors and Hadwiger Conjecture |
| Lecture 40 - More on Graph Minors, Tree Decompositions |
| References |
Graph Theory
Instructor: Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore. An introduction to the subject of graph theory.
|