Middle East Technical University Department of Mathematics     Fall 2008

---

Graph Theory
Math 341

---

Instructor Prof. Sergey Finashin

Textbook   Frank Harary    Graph Theory

---

Syllabus (with pages in the textbook and recommended exercises)

September 15-20) The types of graphs and basic definitions (pp.8-14) 2.1 - 2.5, 2.9, 2.10

September 22-27) Ramsey problem and its variations (pp.15-16) 2.13, 2.15, 2.16, 2.17, 2.19
Extremal problems. Bipartite graphs (pp. 17-18) 2.20, 2,21
October 6-10) Line graphs (pp. 71-72), intersection graphs (p.19), clique graphs (p.20). Cutpoints, bridges and blocks (pp. 26-29) Trees (32-36)

October 13-17) The cycle space. Enumeration of trees. (pp. 37-40, 26-27, 178-179) 3.1-3.4, 3.8, 4.1-4.6, 4.9, 4.11, 4.12, 4.14, 4.15

October 20-24) Connectivity, Menger’s theorem (pp. 43-50) 5.1-5.3, 5.5-5.8, 7.8

October 27-31) Travesability (pp. 64-69) 7.1-7.3, 7.5,7.14,7.15,7.17

Midterm I

November 3-15) Planar graphs, Euler formula, the dual graph. Graphs on surfaces (pp. 102-104, 107-118)

November 17-21) Coloring of vertices, edges and faces of a graph (pp. 5, 126-127, 130-131) 12.11, 12.13

November 24-28) Matrices of graphs (pp. 150-156) 13.1, 13.2

Midterm II

December 1-5) Graphs and groups (160-175)

December 15-20) Digraphs. Other application of graphs

December 27-31) Overview. Reserve.