The course is for students in the second year and higher; it is not an introductory graduate course. The absolute minimum requirement is a good understanding of abstraction and a solid modern algebra background (as from a graduate course), and the more graduate math you know, the better (that's the famous "mathematical maturity"). If you aren't sure whether you might be interested or ready for this class, please see me.
We will use the textbook Graph Theory by Reinhard Diestel, third edition (new in 2005; I recommend against using an earlier edition). The text can be read on line. We will cover as many chapters as we can, which is probably about six. Here is a link to the table of contents. Here is a link to Diestel's list of errata. Here is the link to my list of errata (below, on this page).
I will expect you, the students, to study the material and to work on as many of the exercises as you can. I will meet separately with each student frequently (every week, I hope) to discuss your progress and any questions you or I may have. I will frequently collect written work: see the homework assignments below. I will accept a second version of any problem, if you want to rewrite it for a better grade (or any other reason), but only within a reasonable time (let's say, about two weeks from when I returned the first version).
We meet on MWF 2:20 - 3:20 in LN-2205.
When | Who; what |
2/27, 5:10 | Brett: conclusion of tree and forest packing and covering |
3/6, 5:05 | Keith: path covers of digraphs |
3/20, 5:05 | Justin: structure of factor-critical graphs |
3/27, 5:05 | Garry: the Rado graph |
4/3, 5:05 | Tim: random graphs and a Ramsey number |
4/10, 5:05 | Jackie: list 5-coloring |
4/24, 5:05 | Qing: König's edge coloring theorem |
5/8, 5:10 (postponed from 5/1) | Lucas: tutte invariants |
There is a Combinatorics Seminar that meets usually on Thursdays at 1:15 in LN-2201, but occasionally at a different time; check the schedule. All 510 students are invited to attend (if the room is big enough for 510 students).
All exercises are numbered as in the printed third edition of Diestel's book.
Week of | Topic | Reading sections | Problems to work on | Problems to hand in | ||||
1/23 - 1/27 | Basic concepts: Graphs and multigraphs; Degree; Standard examples | 1.1 - 1.4, 1.10 | Ch. 1 (as many as you can) | |||||
1/30 - 2/3 | Basic concepts: Connectivity; Trees; Biparticity; Minors; Eulerian tours | 1.4 - 1.8 | (ditto) | I. Due 2/1: Ch. 1 ## 3, 4, 16 | ||||
2/6 - 2/10 | Basic concepts: Cycle and cocycle spaces; Matching | 1.9 - 1.10, 2.1 | Ch. 1, 2 (as many as you can; low numbers in Ch. 2) | II. Due 2/15: Ch. 1 ## 15, 20, 24, 27, 31, 35(optional) | ||||
2/13 - 2/17 | Matching | 2.1 - 2.2 | Ch. 2 (as many as you can) | |||||
2/20 - 2/24 | Packing; Connectivity | 2.2 - 2.4, 3.1 | Ch. 2 (as many as you can) | |||||
2/27 - 3/3 | Connectivity: Menger's theorem, Structure | 3.1 - 3.3 | Ch. 3 (as many as you can) | III. Due 2/27: Ch. 2 ## 1, 2, 5, 11, 12, 14 | ||||
3/6 - 3/10 | Connectivity: Menger's theorem Planarity | 3.3, 3.5, 4.1 - 4.2 | Ch. 3, 4 (as many as you can) | |||||
3/20 - 3/24 | Bridges of a subgraph; Planarity: Equivalent embeddings, Kuratowski's theorem | 4.3 - 4.4 | Ch. 4 (as many as you can) | |||||
3/27 - 3/31 | Planarity: Kuratowski's theorem, MacLane's criterion; Projective planarity of signed graphs; Duality | 4.4 - 4.6; Lecture | Ch. 4 (as many as you can) | |||||
4/3 - 4/7 | Coloring: Chromatic polynomial Chromatic number Chromatic index | Lecture; 5.1, 5.3 | Ch. 5 (as many as you can; see below) | |||||
4/10 | Coloring: Chromatic number | 5.1 | Ch. 5 (as many as you can) | IV. Due Wed. 4/12 1:00 sharp: Ch. 3 ## 2, 6, 8, 12, 17, 21 Web I | ||||
4/19 - 4/21 | Coloring signed graphs; Flows: Circulations; Nowhere-zero flows | Lecture; 6.1, 6.3 | Ch. 5 (as many as you can) | V. Due Wed. 4/19: Ch. 4 ## 4, 11 Ch. 5 ## 4, 7 | ||||
4/24 - 4/28 | Nowhere-zero flows: Group flows; Planar duality and 4CT; Conjectures | 6.3 - 6.5 | Ch. 6 (as many as you can) | VI. Due Thurs. 4/27: Ch. 4 ## 20, 23, Web III, Ch. 5 ## 10, 21, Web IV, V | ||||
5/1 - 5/5 | Flows: 6-Flow Theorem; Network flows | 6.6; 6.2 | Ch. 6 (as many as you can) | |||||
5/8 - 5/12 | Forbidden minors: WQOs, Tree decomposition | 12.1, 12.3 | Ch. 12 (some), espec. 12-14, Web I-IV | VII. Due Fri. 5/12: Ch. 5 # Web VI, Ch. 6 ## 9, 15, 18, 19, Web I | ||||