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.

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

Basics

Trees

Matchings

Connectivity