MA6230 GRAPH THEORY
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.
1. D.B. West, Introduction to graph theory, PHI Learning, New Delhi, 2004.
1. J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, GTM Vol. No. 244, Springer 2008.
2. R. Diestel, Graph Theory, Springer, 2006.