MA6230 GRAPH THEORY (modified)
Course Details
Basics: subgraphs, isomorphism, automorphism group, matrices associated with graphs, degrees, walks, connected graphs, shortest path algorithms.
Connectivity: Connectivity and Mengers theorem; Structure of 2-connected and 3-connected graphs, Maders theorem.
Matchings: Berge's theorem, Hall's theorem, Tutte's perfect matching theorem, k-matchings (reduction to perfect matching problem), job-assignment-problem.
Ramsey Theory: Pigeonhole Principle, Ramsey Theorem, Ramsey Numbers.
Eulerian and Hamiltonian graphs: characterization of Euler graphs, necessary/ sufficient conditions for the existence of Hamilton cycles, Fleury's algorithm for eulerian trails, Chinese-postman-problem (complete algorithmic solution), approximate solutions of traveling salesman problem.
Planar Graphs: Euler's formula, Dual graphs, Characerization of planar graphs, planarity testing. Coloring: Brooks' Theorem, Graphs with large chromatic number, Turan's theorem.
Course References:
Text Books:
1. D.B. West, Introduction to graph theory, PHI Learning, New Delhi, 2004.
Reference Books:
1. J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, GTM Vol. No. 244, Springer 2008.
2. J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, GTM Vol. No. 244, Springer 2008.