<h3>MA2130 Basic Graph Theory - [Batches earlier to 2024 only]</h3>
<br/>
<h4>Course Details</h4>
<b>Basics:</b><br> Graphs, subgraphs, isomorphism, representation of graphs, degrees and graphicalsequences, walks, trails, paths, cycles, Connectivity, bipartite graphs.<br> <b>Trees and connectivity:</b><br> Characterizations of trees, minimum-spanning-trees, number of trees, Cayley's formula, shortest path algorithms, cut-sets, Characterization of blocks.<br> <b>Eulerian and Hamiltonian graphs:</b><br> Characterizations, Necessary/sufficient conditions. Coverings and independent sets: Basic relations, matchings in bipartite graphs, Tutte's Perfectmatching theorem and consequences.<br> <b>Colorings:</b><br> Edge-colorings of bipartite graphs, Gupta Vizing's theorem, greedy algorithm for vertex-colorings, Brook's theorem, clique-number and vertex chromatic number. Planar graphs: Euler's formula and its consequences, Kuratowski's Characterization. Directed graphs: Basics, various connectivities and tournaments.<br><br>
<br/>
<h4>Course References:</h4>
TEXT:<br>
J.A Bondy and U.S.R Murthy, Graph Theory with Applications, Macmillan, 1976.<br><br>
REFERENCES:<br>
D.B. West, Introduction to Graph Theory, P.H.I 1999.