**MATH/CS 4690/6690, Spring 2016**

**Instructor: Danny Krashen**

###Basic Information###

**Lecture Schedule**: TuTh 12:30pm - 1:45pm, Boyd 302**Office Hours**: Tu 2:00pm-3:00pm, Boyd 437**Office Phone**: (706) 542-2555**Email**: dkrashen@uga.edu**Course Website**: http://dkrashen.github.io/graphtheory

###Textbooks###

- Suggested Text (not required):
**Graph Theory**, by Bondy and Murty.

Available via Springer, Amazon, UGA Library. - Supplimentary Reading (not required):
**Pearls in Graph Theory**, by Hartsfield and Ringel.

Available via Amazon, Google (ebook), MAA.

###Topical Outline###

- definitions of graphs, digraphs, isomorphisms, degree formula
- subgraphs, unions, intersections
- examples, proof writing
- spanning subgraphs
- trees and algorithms
- graph decompositions, bonds, edge cuts
- walks, cut edges, eulerian tours
- Fleury's algorithm
- cut vertices and blocks
- computational complexity theory
- planar graphs, 4 color theorem
- Ramsey theory
- chromatic numbers and polynomials
- matchings, marraige problem
- edge coloring, scheduling problems, Vizing's theorem
- current research problems in graph theory

###Grading, exams and homework###

The course grade is computed using the following items:

- Two mid-semester exams worth 25% each
- Weekly homework worth 20%
- Final exam worth 30%

The final exam is optional for those students with a grade of at least A- going into the final.

###Academic Honesty###

As a University of Georgia student, you have agreed to abide by the University's academic honesty policy, "A Culture of Honesty," and the Student Honor Code. All academic work must meet the standards described in "A Culture of Honesty," which can be found at: http://www.uga.edu/honesty. Lack of knowledge of the academic honesty policy is not a reasonable explanation for a violation. Questions related to course assignments and the academic honesty policy should be directed to the instructor.

*The course syllabus is a general plan for the course; deviations
announced to the class by the instructor may be necessary.*