Welcome to MA6230 graph theory home page. Here you will find syllabus, notes and other useful information.
Introduction : Graphs, Degree sequence, connected graphs, paths, cycles, distance, cut-vertex, bridges, blocks, isomorphism.
Trees and connectivity:
Trees, properties of trees, counting trees.
Vertex connectivity, edge connectivity.
Mengers theorem.
Eulerian graphs and hamiltonian graphs:
Eulerian graphs, hamiltonian graphs, characterizations.
Definition of Line graphs.
Matching : Hall's theorem. Realated algorithmic questions.
More algorithms:
BFS, DFS,
Minimum spanning tree problem: greedy algorithm.
Kruskal's and Prims algorithms. Dijkstra's Shortest path algorithm.
Planar graphs and graph coloring : Planarity and characterizations.
Five colour theorem. Four colour theorem. Proof idea: Discharging method.
Colouring: Greedy colouring, Brooks theorem.
Edge colouring: Konig's theorem for bipartite graphs, Vizings algorithm. List colouring: 5-choosability of planar graphs.
Vertex cover, Independent set, max clique problems.:
Matching based algorithm.
Forbidden substructure characterization:
Perfect graphs:Perfect graph theorem.
strong perfect graph theorem.
Chordal graphs: intersection representation. Maximum cardinality search algorithm and Tarjan's theorem.
This notes are due to Matt DeVos of Simon Fraser Universirty Canada available from his web page "http://www.sfu.ca/~mdevos/" . It may use slightly different notation and may contain some typos and may cover a bit different sub topics. But should give you a good idea for recap. Many thanks to Matt. We will replace it by our own notes once they are ready.
Basics
Trees
Matchings
Connectivity
