x
Menu

Graph Theory

IISc Bangalore, , Prof. L. Sunil Chandran

Updated On 02 Feb, 19

Overview

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

Includes

Lecture 13: Vertex coloring Brooks theorem

4.1 ( 11 )


Lecture Details

Graph Theory by Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore. For more details on NPTEL visit httpnptel.iitm.ac.in

Ratings

4.0


4 Ratings
55%
30%
10%
3%
2%
Comments
comment person image

Sam

Excellent course helped me understand topic that i couldn't while attendinfg my college.

Reply
comment person image

Dembe

Great course. Thank you very much.

Reply
Send