CSC 2410H - Introduction to Graph Theory - Winter 2004


Lecture: Thursday 10 - 12, in PA70

Instructor: Avner Magen,

Office hours: Thursday 14-16 (Sandford Fleming 2304D, 416-946-8672).

Tutor: Lap Chi Lau,

Books: main text : West, Introduction to graph thepry, 2nd edition.
Others: Gibbons, Algorithmic graph theory. Bondy and Murty, Graph theory with applications.


    Course Requirements

There will be a total of three assignemnts and an exam. The (combined) weight of the assignments is 50% and the weight of the exam is 50%.


    Announcements

final grades are available! You can check the list on my door (SF 2304D). Disclaimer - these are not yet the official and approved grades.

    Exercises

exercise #1 and its solution

exercise #2 and its solution

exercise #3 and its solution



    Material

Next class

Probabilistic tools to sow concentration. Abundance of expander graphs. Threshold phenomena.

Covered so far

Isomorphism. Graphical degree sequences, Havel-Hakimi thm, Erdos Gallai (no proof).
k-partite graphs, Turan's thm. subgraphs : spanning and induced. Trees. Minimum Spanning Trees. Kruskal's and Prim's algorithms.
Distances in graph. Shortest Path algorithms. Matching. Maximum matching, augmenting paths, Hall's thm, marriage thm. Minmax theorems and some LP concepts (duality, relaxation). vertex-cover. Konig thm on vertex cover in bipartite graphs.
finding maximum bipartite matching, finding maximum weight bipartite mathching Tutte's theorem and applications, Edmond's blossom alg.
vertex/edge-connectivity, block-structure. Menger's thm. Network flows. Ford-Fulkerson alg for max-flow, min-cut max-flow thm, applications : Menger's (edge and vertex versions) and Hall's thm. Multicommodity flows and demands of cuts. mincut-maxflow version of Leighton-Rao, London-Linial-Rabinovich.
Colouring. Greedy colouring. Brooks' thm, Mycielski's thm, Wigderson's alg for colouring a 3-colourable graph in sqrt{n} colours, colour-critical graphs. Perfect Graphs.
Planarity. Eule'sr formula, Kuratowski's thm. 5-colour thm, 4-colour thm (no proof). planarity testing, embedding graphs to other surfaces and Robertson-Seymor thm.
Edge colouring. Vizing's theorem. Hamiltonain cycles.
The probabilistic method in graphs. Random graphs. lower bound on Ramsey numbers. independence number in sparse graphs. crossing number in dense graphs. graphs with large girth and large chromatic number.

Syllabus

Notice : the material actualy covered will be some subset of these topics, and definitely not all.

  • graphs, subgraphs, isomorphism, degree sequences : Havel-Hakimi, Erdos-Gallai, Turan theorem.

  • TREES: enumeration of trees, Minimum spanning tree, MST algorithms (Kruskal, Prim), distances in graphs, shortest path algorithms (Dijkstra, Bellman).

  • MATCHING : maximum matching, augmenting paths, perfect matching. Hall's thm, vertex and edge covers, Gallai thm. bipartite matching (algorithmic aspects), Gale-Shapley stabe marriage. Tuttes theorem, f-factors. Edmond's algorithm.

  • connectivity (edge and vertex). k-connectivity. Menger's theorem. Network flows. Ford-Fulkerson. mincut max flow. integral flows. application to flows. Sparsest cut and Multicommodity flows. Leighton-Rao theorem.

  • COLOURING: vertex colouring. Brook's theorem. chromatic polynomial. Lovasz's Theta function. perfect graph thm.

  • PLANAR GRAPHS. Eule'sr formula. characterization. Kuratowski's theorem. planarity testing. four colour thm. Klein Plotkin Rao.

  • edge colouring. Hamiltonian cyclces.

  • NP-hard problems. approximation algorithms for graph-problems. vertex-cover.

  • Extras : Random graphs. algebraic graph theory. expander graphs.