MA5011 Advanced Graph Theory
Course Details
Review of graphs:
Connectivity and Mengers theorem. Structure of 2-connected and 3-connected graphs, Maders theorem.
Basic counting:
Corradi's Lemma. Turan's theorem, Dirichlet's theorem, Erdos-Szekeres theorem. Hall's theorem. Sunflower Lemma and applications, Erdos-Ko-Rado theorem.
Vertex and Edge colouring:
Planar graphs, Kuratowski's theorem, Four color theorem, Discharging Method and applications, Tait's theorem. Intersection edge colourings, List colouring conjecture: Galvin's result.
Extremal graphs:
Ramsey theory, Ramsey number R(p,q). Intersection number, Erdos-Goodman-Posa theorem. Interval graphs, boxicity. Partition using paths and cycles, Erdos-Gallai theorem, Bondy's theorem.
Probabilisitc Method and Random graphs:
Lovasz Local Lemma, Second Moment method, Concentration results. Caros theorem, Erdos theorem (girth and chromatic number), Szele theorem. Random graph models, properties for almost all graphs, evolution and threshold functions, connectivity of random graphs.
Course References:
Text Books:
1. Extremal Combinatorics: Stasys Jukna, Springer. 2001.
2. The Probabilistic Method: Noga Alon, Joel Spencer, Wiley. 2000.
3. Random graphs: Bela Bollobas, Cambridge. 2004.
References:
1. Extremal Graph Theory: Bela Bollobas, Dover. 1978.
2. Introduction to Graph Theory: D B West, Prentice Hall India. 2001.
3. Graph Theory: Reinhard Diestel, Springer. 2006.