IISc Bangalore Course , Prof. L. Sunil Chandran

**246**students enrolled

IISc Bangalore Course , Prof. L. Sunil Chandran

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

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

Up Next

You can skip ad in

SKIP AD >

Advertisement

- 2x
- 1.5x
- 1x
- 0.5x
- 0.25x

EMBED LINK

COPY

DIRECT LINK

COPY

PRIVATE CONTENT

OK

Enter password to view

Please enter valid password!

- Play Pause
- Mute UnMute
- Fullscreen Normal
- @Your Company Title

0:00

3.3 (24 Ratings)

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

Heads up!

These lecture videos are delivered by IISc Bangalore, under the NPTEL program, lot of nptel video courses are available for learning online.
29%

33%

4%

8%

25%

- 1.Introduction Vertex cover and independent set
- 2.Matchings Konigs theorem and Halls theorem
- 3.More on Halls theorem and some applications
- 4.Tuttes theorem on existence of a perfect matching
- 5.More on Tuttes theorem
- 6.More on Matchings
- 7.Dominating set, path cover
- 8.Gallai -- Millgram theorem, Dilworths theorem
- 9.Connectivity 2-connected and 3- connected graphs
- 10.Mengers theorem
- 11.More on connectivity k- linkedness
- 12.Minors, topological minors and more on k- linkedness
- 13.Vertex coloring Brooks theorem
- 14.More on vertex coloring
- 15.Edge coloring Vizings theorem
- 16.Proof of Vizings theorem, Introduction to planarity
- 17.5- coloring planar graphs, Kuratowskys theorem
- 18.Proof of Kuratowskys theorem, List coloring
- 19.List chromatic index
- 20.Adjacency polynomial of a graph and combinatorial Nullstellensatz
- 21.Chromatic polynomial, k - critical graphs
- 22.Gallai-Roy theorem, Acyclic coloring, Hadwigers conjecture
- 23.Perfect graphs Examples
- 24.Interval graphs, chordal graphs
- 25.Proof of weak perfect graph theorem (WPGT)
- 26.Second proof of WPGT, Some non-perfect graph classes
- 27.More special classes of graphs
- 28.Boxicity,Sphericity, Hamiltonian circuits
- 29.More on Hamiltonicity Chvatals theorem
- 30.Chvatals theorem, toughness, Hamiltonicity and 4-color conjecture
- 31.Network flows Max flow mincut theorem
- 32.More on network flows Circulations
- 33.Circulations and tensions
- 34.More on circulations and tensions, flow number and Tuttes flow conjectures
- 35.Random graphs and probabilistic method Preliminaries
- 36.Probabilistic method Markovs inequality, Ramsey number
- 37.Probabilistic method Graphs of high girth and high chromatic number I
- 38.Probabilistic method Second moment method, Lovasz local lemma II
- 39.Graph minors and Hadwigers conjecture
- 40.More on graph minors, tree decompositions

- FreeVideoLectures aim to help millions of students across the world acquire knowledge, gain good grades, get jobs, assist in getting promotions through quality learning material.

- You can write to us
- help@freevideolectures.com

2018 FreeVideoLectures. All rights reserved. FreeVideoLectures only promotes free course material from different sources, we are not endrosed by any university.