CIS 4560 Graph Theory

Instructor: Chip Klostermeyer 	e-mail: wkloster@unf.edu
                                URL: http://www.unf.edu/~wkloster
Office: 15/3224 		Phone: 620-2985
Office Hours: TR 3:30-6:00

Text (required):  Introductory Graph Theory, by Chartrand and Zhang
Prerequisite: COT 3100, programming experience.

Overview:  Graph theory is a very active area of study among
mathematicians and computer scientists. Graphs can be used
to model many real-world phenomena (e.g. computer networks, 
highway systems, scheduling problems) and graph algorithms have
many applications. We shall study classical, "structural," 
graph theory as well as some important graph algorithms.

Goals and Objectives: To improve one's mathematical skills, 
to understand classical graph theory and its applications in
the field of computing. To be able use graph theory to model
and solve problems in computing.

Method of Evaluation: Letter grades will be assigned based on:
	2 Midterms (25% each), Final exam (30%), 
	One Programming Assignment (15%), Mini-Paper (5%),
        Homework (0%)

Graduate Students *must* complete two mini-papers as well
as write a detailed description of one of the open problems
listed on the unsolved problems link. Grade will be reduced
one-half letter grade for each not completed successfully.

Several homework problems will be assigned roughly once a week.
Many will be discussed in class, some will be collected. You are 
encouraged to discuss your solutions in class or with the instructor 
during office hours. A math class is likea music class, you must practice 
in order to do well!

We will devote some class periods  to working problems (both those
assigned and additional problems). You should keep a notebook or folder 
with all your homework solutions in it.

Mini-paper: Read a paper on some graph theory topic from any of
the following journals: Discrete Mathematics, Journal of Graph
Theory, Journal of Combinatorial Theory B. In ~2 pages of your
own words, describe the problem, give an example, and explain the
main results. [Due: before scheduled final exam]

Scale: 90%=A, 80%=B, 70%=C, 60%=D, though these may be scaled 
downward if necessary (i.e., a score less than 90% may merit an "A'"). 

NO MAKE-UP EXAMS WILL BE GIVEN.
NO Grades of "Incomplete" will be given except for those
   who circumstances fall under university/dept. criteria.

Honesty Statement: You are expected to do your own work. 
Any violation of academic integrity (copying, plagiarism, 
cheating, submitting work that is not completely one's own, etc.) 
shows lack of respect for me and will be dealt with in 
accordance with university policy.

Outline (approximate time schedule):

        	Review of Proofs, Sets, etc.    	1 week
	  	Fundamentals				3 weeks
			(Paths, Circuits, Degrees, 
                 	Digraphs, Proofs)
		Coloring				3 weeks
			(Vertex coloring, circular coloring, planar 
			graph coloring, list coloring, Kuratowski's 
			theorem, sub-classes of planar graphs)
		Connectivity				1 week
			(Menger's theorem, Max-Flow/Min-Cut Theorem)		
	        Matching, Stable Marriage               1 week
	        Algorithms and Applications		1-3 weeks
	        Dominating Sets, Hamiltonian Cycles 	2-4 weeks
		Other topics				as time permits

Final exam will be given at scheduled time.