Lecture 21 of 40Coloring
Chromatic polynomial, k - critical graphs
Dr. L. Sunil Chandran · IISc Bangalore
Credits and licence
- From
- Graph Theory, IISc Bangalore (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Introduction: Vertex cover and independent set
- Matchings: Konigs theorem and Halls theorem
- More on Halls theorem and some applications
- Tuttes theorem on existence of a perfect matching
- More on Tuttes theorem
- More on Matchings
- Dominating set, path cover
- Gallai : Millgram theorem, Dilworths theorem
- Connectivity: 2-connected and 3- connected graphs
- Mengers theorem
- More on connectivity: k- linkedness
- Minors, topological minors and more on k- linkedness
- Vertex coloring: Brooks theorem
- More on vertex coloring
- Edge coloring: Vizings theorem
- Proof of Vizings theorem, Introduction to planarity
- 5- coloring planar graphs, Kuratowskys theorem
- Proof of Kuratowskys theorem, List coloring
- List chromatic index
- Adjacency polynomial of a graph and combinatorial Nullstellensatz
- Chromatic polynomial, k - critical graphs
- Gallai-Roy theorem, Acyclic coloring, Hadwigers 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: Chvatals theorem
- Chvatals 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 Tuttes flow conjectures
- Random graphs and probabilistic method: Preliminaries
- Probabilistic method: Markovs inequality, Ramsey number
- Probabilistic method: Graphs of high girth and high chromatic number
- Probabilistic method: Second moment method, Lovasz local lemma
- Graph minors and Hadwigers conjecture
- More on graph minors, tree decompositions