Kevin Milans : Teaching : Fall 2018 Math573: Graph Theory

Kevin Milans (milans@math.wvu.edu)
Office: Armstrong Hall 408H
Office Hours: MW 2:30pm-3:20pm, Thurs 11:30am-12:30pm, and by appointment
Class Meetings: MWF 11:30am-12:20pm in Armstrong Hall 120
Home | Course Syllabus (PDF) | Homework

Course Schedule

No. Date Class Summary Section(s) Comments
1 Aug 15 Introduction; Definitions and basic concepts 1.1 HW1 assigned.
2 Aug 17 Cliques and Independent sets; important graphs; isomorphism 1.1 -
3 Aug 20 Decompositions; Petersen graph 1.1 -
4 Aug 22 Walks, trails, paths; components; cut-vertices and cut-edges 1.2 -
5 Aug 24 Cut-edge characterization; lemmas on walks 1.2 -
6 Aug 27 Bipartite graph characterization; Eulerian circuits 1.2 -
7 Aug 29 Eulerian Circuits; Eulerian graph characterization 1.2 -
8 Aug 31 Decomposing G into trails; degree-sum formula; hypercubes 1.2,1.3 HW1 due; HW2 assigned.
9 Sep 5 Algorithmic proofs; Mantel's Theorem 1.3 -
10 Sep 7 The Induction Trap; Havel--Hakimi 1.3 -
11 Sep 10 Havel--Hakimi; connectedness of 2-switch graph 1.3 -
12 Sep 12 Directed graphs; deBruijn cycles 1.4 -
13 Sep 14 Trees 2.1 HW2 due; HW3 assigned.
14 Sep 17 Spanning tree application: A game on graphs - -
15 Sep 19 Spanning trees: Cayley's Formula - -
16 Sep 21 Matchings; Maximum vs. Maximal; Alternating paths 3.1 -
17 Sep 24 Hall's Theorem 3.1 -
18 Sep 26 Midterm Exam - -
19 Sep 28 Vertex covers; Konig--Egervary Thm 3.1 -
20 Oct 1 Graph optimization parameters 3.1 HW3 due; HW4 assigned.
21 Oct 3 Tutte's Theorem 3.3 -
22 Oct 5 Tutte's Thm: applicatons; Connectivity 3.3,4.1 -
23 Oct 8 Vertex and Edge connectivity 4.1 -
24 Oct 10 Vertex and Edge connectivity II; Bonds; Blocks 4.1 -
- Oct 12 Fall Break: no class - -
25 Oct 15 Blocks; 2-connected graphs 4.1,4.2 HW4 due. HW5 assigned.
26 Oct 17 Ear Decompositions 4.2 -
27 Oct 19 Block cut-point graph 4.2 -
28 Oct 22 Menger's Theorem 4.2 -
29 Oct 24 Network flows and cuts 4.3 -
30 Oct 26 Ford--Fulkerson Algorithm; Max-flow/Min-cut Thm 4.3 -
31 Oct 29 Vertex coloring 5.1 HW5 due. HW6 assigned.
32 Oct 31 Vertex coloring II 5.1 -
33 Nov 2 Vertex coloring III 5.1 -
34 Nov 5 Brooks's Theorem 5.1 -
35 Nov 7 Mycielski's Construction 5.2 -
36 Nov 9 Large Girth and Large Chromatic Number; Turan's Theorem 5.2 -
37 Nov 12 Erdos--Stone--Simonovits; Turan Numbers for C4 - -
38 Nov 14 Subdivisions and Minors; Hajos and Hadwiger 5.2 HW6 due.
39 Nov 16 Planar Graphs I 6.1 HW7 assigned.
40 Nov 26 Planar graphs II; outerplanar graphs 6.1 -
41 Nov 28 Euler's formula; regular polyhedra 6.1 -
42 Nov 30 Kuratowski's Theorem; Coloring of planar graphs 6.2,6.3 -
43 Dec 3 List coloring; planar graphs are 5-choosable - -
44 Dec 5 Edge colorings; spanning cycles 7.1,7.2 HW7 due.
- Dec 13 Final Exam: Thurs Dec 13, 11am to 1pm - -
milans@math.wvu.edu