GRAPH THEORY
(MATH 3116-001, Fall 2011)

Instructor: Gábor Hetyei
Office: Fretwell 335F, Phone: 687-1045, E-mail: ghetyei@uncc.edu
Office hours: MW 2:00-3:00 pm or by appointment (eventual changes will be announced in class).
Text: Applied Combinatorics, 6th Edition by Alan Tucker. ISBN 978-0-470-45838-9.
Some information will be available on supplementary handouts, and you can not expext everything told in the lecture to be found in the book. Attendance is mandatory!
Prerequisite: MATH 2164, or consent of the department.
Topics: Chapter 1: Graph models, isomorphism, edge counting, planar graphs
Chapter 2: Euler cycles, graph coloring
Chapter 3: Properties of trees, spanning trees
Chapter 4: shortest paths, minimum spanning trees, network flows, algorithmic matching.

Time permitting, and depending on the interest of the audience, we will also cover some of the following: Hamilton circuits (Ch. 2), search trees, the traveling salesperson problem (Ch. 3), the transportation problem (Ch. 4).
Test Dates:
Test 1 Monday, September 23, 2013.
Test 2 Wednesday, October 30, 2013.
Final Exam Monday, Dec 9, 5:00-7:30 pm.
(Double-check in the UNCC Final Exam schedule !)
The final exam will be cumulative, consisting of two parts. The first part will be mandatory, covering only material taught after Test 2. The second half will contain questions reviewing the material taught before Test 2. This part will be optional, if left unanswered, I will substitute the average of your test scores.
Homework: Homework will be assigned nearly every day, and will be usually collected on Monday. I will make an effort to regularly post the homework on the webpage
http://math2.uncc.edu/~ghetyei/courses/3116/hw.html
In case of discrepancy, what I said in class is "official". A random selection of the assigned exercises will be graded. Past due assignments will be counted at the rate of 90% of their value. No credit will be given for solutions submitted after we discussed them in class.
Evaluation: Grades will be based on: 23% for the homework, 22% for each of the tests, and 33% for the final (22% for the mandatory part, 11% for the optional part).
Class meeting: MW 5:00 pm - 6:15 pm in Fretwell 306.
Homepage: http://math2.uncc.edu/~ghetyei/courses/3116/index.html