0

(

ratings

)

2

students

Created by:

Profile Photo

Last updated:

September 25, 2023

Duration:

Unlimited Duration

FREE

This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration

Description




















Graph Theory. Instructor: Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore



Graph Theory. Instructor: Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore.




































































































































































































































































































































































































































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)

Course Curriculum

    • Lecture 01 – Introduction to Cryptography Unlimited
    • Lecture 02 – Matchings: Konig’s Theorem and Hall’s Theorem Unlimited
    • Lecture 03 – More on Hall’s Theorem and Some Applications Unlimited
    • Lecture 04 – Tutte’s Theorem on Existence of a Perfect Matching Unlimited
    • Lecture 05 – More on Tutte’s Theorem Unlimited
    • Lecture 06 – More on Matchings Unlimited
    • Lecture 07 – Dominating Set, Path Cover Unlimited
    • Lecture 08 – Gallai-Milgram Theorem, Dilworth’s Theorem Unlimited
    • Lecture 09 – Connectivity: 2-Connected and 3-Connected Graphs Unlimited
    • Lecture 10 – Menger’s Theorem Unlimited
    • Lecture 11 – More on Connectivity: K-Linkedness Unlimited
    • Lecture 12 – Minors, Topological Minors and More on K-Linkedness Unlimited
    • Lecture 13 – Vertex Coloring: Brooks’ Theorem Unlimited
    • Lecture 15 – Edge Coloring: Vizing’s Theorem Unlimited
    • Lecture 16 – Proof of Vizing’s Theorem, Introduction to Planarity Unlimited
    • Lecture 17 – 5-Coloring Planar Graphs, Kuratowski’s Theorem Unlimited
    • Lecture 18 – Proof of Kuratowski’s Theorem, List Coloring Unlimited
    • Lecture 19 – List Chromatic Index Unlimited
    • Lecture 20 – Adjacency Polynomial of a Graph and Combinatorial Nullstellensatz Unlimited
    • Lecture 22 – Gallai-Roy Theorem, Acyclic Coloring, Hadwiger Conjecture Unlimited
    • Lecture 23 – Perfect Graphs: Examples Unlimited
    • Lecture 24 – Interval Graphs, Chordal Graphs Unlimited
    • Lecture 25 – Proof of Weak Perfect Graph Theorem (WPGT) Unlimited
    • Lecture 26 – Second Proof of WPGT, Some Non-perfect Graph Classes Unlimited
    • Lecture 27 – More Special Classes of Graphs Unlimited
    • Lecture 28 – Boxicity, Sphericity, Hamiltonian Circuits Unlimited
    • Lecture 30 – Chvatal’s Theorem, Toughness, Hamiltonicity and 4-Color Conjecture Unlimited
    • Lecture 31 – Network Flows: Max-Flow Min-Cut Theorem Unlimited
    • Lecture 32 – More on Network Flows: Circulations Unlimited
    • Lecture 33 – Circulations and Tensions Unlimited
    • Lecture 34 – More on Circulations and Tensions, Flow Number and Tutte’s Flow Conjectures Unlimited
    • Lecture 35 – Random Graphs and Probabilistic Method: Preliminaries Unlimited
    • Lecture 36 – Probabilistic Method: Markov’s Inequality, Ramsey Number Unlimited
    • Lecture 37 – Probabilistic Method: Graphs of High Girth and High Chromatic Number Unlimited
    • Lecture 38 – Probabilistic Method: Second Moment Method, Lovasz Local Lemma Unlimited
    • Lecture 39 – Graph Minors and Hadwiger Conjecture Unlimited
    • Lecture 40 – More on Graph Minors, Tree Decompositions Unlimited

About the instructor

5 5

Instructor Rating

6

Reviews

4637

Courses

24151

Students

Profile Photo
OpenCoursa
We are an educational and skills marketplace to accommodate the needs of skills enhancement and free equal education across the globe to the millions. We are bringing courses and trainings every single day for our users. We welcome everyone woth all ages, all background to learn. There is so much available to learn and deliver to the people.