Math 7405 Advanced Graph Theory

Spring 2016 Section 001

    None currently.

Course Materials:
    Syllabus and course log recording topics covered in each lecture.
    Textbook: prepublication version of Extremal Graph Theory by D.B. West.

homework #1 revised
homework #2
homework #3
homework #4

Topics/papers for presentations:
  • Algorithmic aspects of coloring: backtracking search, LP formulation, column generation (JT, Mar 9)
  • Discharging: O. V. Borodin, A. N. Glebov, A. Raspaud, and M. R. Salavatipour. Planar graphs without cycles of length from 4 to 7 are 3-colorable. J. Combin. Theory Ser. B, 93(2):303--311, 2005.
  • Inductive proofs for coloring planar graphs: list-coloring version of Grotzsch's theorem, by Thomassen or Dvorak (DT)
  • Combinatorial Nullstellensatz: Noga Alon, Combinatorial Nullstellensatz, Recent trends in combinatorics (Mátraháza, 1995). Combin. Probab. Comput. 8 (1999), no. 1-2, 7–29. Preprint available on his webpage. (NG)
  • Regularity lemma:

Additional references:
    Stephen Hartke, (appropriately changed)
    Office: Student Commons Building Room AB1-4303
    Office Hours: Tues/Thurs 2:00-3:15pm, or by appointment.
Meeting Times:
    Mon/Wed 2:00-3:15pm, Student Commons Building Room AB1-4113
Old Announcements:
(Feb 8) For Homework #1, do problems 3.4.11, 3.4.23, 3.4.20, and 3.4.35 (these were 1,2,3,5 on the original assignment). Homework #1 is due on Wed Feb 10. The other problems will be added to the next homework assignment.

    Back This page last modified .