APM 569, Graph Theory and Applications, 4 credits—Winter 2007

• Detailed syllabus for the course.
• Place and Time: Tue, Thu at 7:30–9:17 PM in DHE 236.

• Office hours: Mon, Wed 3:00–4:00 PM, or by appointment (SEB 347).
  During office hours I let everyone who showed up into my office and discuss questions in a round-robin manner. If you would like a one-to-one meeting, e-mail me to set up an appointment.

• Textbook: Introduction to Graph Theory by Douglas B. West (2nd edition, Prentice-Hall, 2001, ISBN: 0-13-014400-2). Used copies of the second edition can be found at Amazon.com. I expect you to have a copy of this textbook.

• Homework Assignments:
  There will be a couple of homework assignments. Your solutions should be nicely presented. Write as clearly and cleanly as you can, use sentences, and explain the steps of the solution. I encourage you to work in groups and discuss the problems and their solutions with each other. However, the actual solutions you submit should be your own work (see Academic honesty for more info).
  • Assignment #3.
    Due date: Tue, Mar 6, 2007.
    
  • Assignment #2.
    Due date: Tue, Feb 13, 2007.
    
  • Assignment #1.
    Due date: Tue, Jan 30, 2007.
    

• Final Exam: There will be no tests or final exam in this course.

• Project: There will be a project instead of a final exam. You will need to choose a paper published in a mathematics or computer science research journal (or conference proceedings) within the past 15 years, prepare a written report on it, and present it in class. The paper should have appeared in Mathematical Reviews (use an OU machine to have access). You will need to understand the paper and convey that understanding to the rest of the class. The written report should be about 5–10 pages, and it should include the main idea of the paper, and, in your own words, at least an outline of the proofs of the major results in the paper, as well as discussion of the background and setting for this work (this involves looking at some of the references). The oral presentations will take about 50 minutes each during the last couple of weeks of classes. Your goal is to explain what the paper achieves, why it is important and where it might lead. Give some background (motivation for the paper), concentrate on examples, and go through some of the proofs. You might want to prepare a brief handout so we have some of the definitions and lemmas at hand. Discuss your choice of the paper by the end of February, before the winter break, so I can approve it.

• Material covered:

  Week	Dates	Material covered	Section
  1	Jan 1–5	Discussion of syllabus	-
  2	Jan 8–12	Extremal graphs Matchings and covers	Section 1.3, pages 38–44 Section 5.2, pages 207–210 Section 3.1, pages 107–115
  3	Jan 15–19	Faster bipartite matchings, Ass. #1 Weighted matchings and covers	Section 3.2, pages 132–134 Section 3.2, pages 125–130
  4	Jan 22–26	Stable matchings Matchings in nonbipartite graphs	Section 3.2, pages 130–132 Section 3.3, pages 136–140
  5	Jan 29–Feb 2	Flows, Ass. #2 Flows with lower and upper bounds	Section 4.3, pages 176–180 Section 4.3, pages 184–187
  6	Feb 5–9	Vertes colorings Edge colorings	Section 5.1, pages 191–199 Section 5.2, pages 204–206 Section 7.1, pages 273–279
  7	Feb 12–16	Hamiltonian cycles, Ass. #3	Section 7.2, pages 286–293
  8	Feb 19–23	Perfect graphs	Section 8.1, pages 319–323
  9	Feb 26–Mar 2	Winter Break	-
  10	Mar 5–9	Matroids	Section 8.2, pages 349–354
  11	Mar 12–16	Properties of matroids Matroid intersection	Section 8.2, pages 354–358, 360–364, 366–367
  12	Mar 19–23
  13	Mar 26–30	Presentations
  14	Apr 2–6	Presentations
  15	Apr 9–13	Presentations
  16	Apr 16–20	Presentations

• Academic honesty:
  Cheating is a serious academic crime. Oakland University policy requires that all suspected instances of cheating be reported to the Academic Conduct Committee for adjudication. Anyone found guilty of cheating in this course will receive a course grade of 0.0 in addition to any penalty assigned by the Academic Conduct Committee. Working with others on an assignment does not constitute cheating (unless explicitly forbidden), handing in an assignment or program that has essentially been copied from someone else does.