CS60047 Advanced Graph Theory - Winter 2019
Instructor:
Prof. Bhargab B. Bhattacharya and Palash Dey
Teaching Assistants:
Minu Tiwari (minutiwari@iitkgp.ac.in)
Sumeet Shirgure (sumeetshirgure@iitkgp.ac.in)
Course overview:
- Fundamental concepts of graphs: Basic definitions, graphs and digraphs,
properties, subgraphs, complementation; Incidence and adjacency matrices;
Complete graphs, regular graphs; Petersen graph; Handshaking lemma; Bipartite
graphs, Mantel’s Theorem; Ramsey number, Turan’s Theorem; Isomorphism of
graphs.
- Connectivity: Vertex and edge connectivity, Cliques and independent sets;
connected components, paths and cycles, cuts, blocks, k-connected graphs;
Menger's theorem; diameter and shortest paths.
- Trees and forests: centers and centroids; spanning trees, Steiner trees; tree
enumeration; Cayley’s theorem; Prüfer codes.
- Traversability: Eulerian and Hamiltonian graphs; Dirac’s theorem; Fleury’s
algorithm for finding Eulerian paths or cycles; Traveling Salesman problem,
Chinese Postman Problem.
- Directed graphs: Tournaments, directed paths and cycles, Eulerian digraphs,
connectivity and strongly connected digraphs; directed acyclic graphs (DAG),
topological sorting.
- Planarity: Plane and planar graphs, outerplanar graphs, maximal planar graphs,
Non-planarity of K 5 and K 3,3 ; Kuratowski’s theorem; planar dual; Euler’s formula.
Tait’s conjecture; Planar embedding of trees and graphs; genus, thickness, and
crossing number; Planar separability theorem.
- Matching and covering: Maximum matching, Berge’s theorem; perfect
matching; Matching in bipartite graphs - Konig's theorem, Hall's marriage
theorem; Matching in general graphs - Tutte's theorem; weighted matching;
sketch of matching algorithms; Path covering - Gallai-Milgram theorem, Dilworth
theorem.
- Coloring: Vertex and edge coloring, clique number and chromatic number;
vertex colouring - Brooks'; theorem, Edge colouring - Vizing's theorem; Five colour
theorem for planar graphs; Four-color theorem for planar graphs; Wells-Powell
algorithm for graph coloring; 3-colorability of triangulated polygons, art-gallery
problem.
- Network flows: Flows and matching; max-flow min-cut theorem.
- Intersection graphs and perfect graphs: Interval graphs, comparability graphs,
permutation graphs, chordal graphs; circle graphs, circular arc graphs;
Applications to electronic design automation.
- Selected topics: Reconstruction problem in graph theory, Random graphs.
Classes:
Venue: CSE-119. Timings: Wednesday (12 PM - 12:55 PM) and Friday (9 AM - 10:55 AM)
Grading:
- In-Class Quiz and Homework for practicing
- Class-Test 1 and Class-Test 2 (90 min each): 20% (=10 * 2)
- Mid-Sem Exam (2 hour): 30%
- End-Sem Exam (3 hour): 50%
Announcements:
- Question papers: final, midsem, second class test, first class test set
- Please click here to join the course Google group. If you face any issue joining this group, please send an email to the TAs writing your name and roll number.
- Class-Test 1 (Credit 10%) will be held on Friday, 06 September
2019, 9:15 - 10:45 (Rm CSE 119) - Open Book/Notes.
- Class-Test 2 (Credit 10%) will be held on Wednesday, 23rd October 2019, 12 - 12:55 (Room CSE 119)
Assignments:
- Homework 1 (due in the week beginning 29 July 2019)
Problem 1.1.5, 1.1.6, 1.1.8, 1.1.11, 1.1.18, 1.2.28, 1.2.29 from the
textbook (D. West).
Solutions will be discussed in the tutorial class.
- Homework 2 posted here. Due on August 14.
- Homework 3 & 4 (Due Sept 05, 2019)
From DW's text book - Problem # 1.2.34, 2.3.23, 3.1.54, 3.1.55,
3.1.59, 7.2.3, 7.2.4, 7.2.12
References:
- Douglas B. West: Introduction to Graph Theory, Second Edition, Pearson,
Singapore, 2000.
- Arthur Benjamin, Gary Chartrand, and Ping Zhang: The Fascinating World of
Graph Theory, Princeton University Press, 2015.
- R. Diestel: Graph Theory.
- Frank Harary: Graph Theory, CRC Press, 2018 (originally published in 1969).
- Paul Zeitz: The Art and Craft of Problem Solving, Third Edition, Wiley, 2016.
- Narsingh Deo: Graph Theory with Applications to Engineering & Computer
Sciences, Prentice Hall, 1974.
- J. A. Bondy and U.S.R. Murty: Graph Theory, Springer, 2008.
- Reinhard Diestel: Graph Theory, Springer, 2000.
- Anany Levitin and Maria Levitin: Algorithmic Puzzles, Oxford, 2011.
- M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, North Holland,
Second Edition, 2004.
- Christopher Griffin: Graph Theory: Penn State Lecture Notes, 2011-2017.