Tuesday 7/6: Distributed handout on Ramsey
theory. Continued discussion of Ramsey theory, began review for the final.
Thursday 7/1: Distributed review problems for the final exam. Topics covered:
proof of Max-Flow-Min-Cut Theorem, augmenting flows, introduction to Ramsey
theory. Relevant book sections: 29.
Wednesday 6/30: Returned HW #4. Tomorrow's office hours are cancelled.
Topics covered: corollaries of Menger's theorem, networks, flows in
networks, statement of Max-Flow-Min-Cut Theorem. Relevant book sections:
28,29.
Tuesday 6/29: Collected HW #4 and distributed HW #5.
Note that HW #5 is due next Wednesday, not Tuesday.
Also distributed handout on Tutte's theorem.
Topics covered: digraphs, orientable graphs, tournaments; vw-disconnecting
sets, vw-separating sets, Menger's theorem. Relevant book sections:
22,23,28.
Monday 6/28: Topics covered: Tutte's theorem, matchings in bridgeless cubic
graphs; introduction to directed graphs-- basic definitions. Relevant book
sections: 22,23.
Thursday 6/24: Scheduling note: there will be no class Monday 7/5. Topics
covered: Konig-Egervary theorem, Hungarian algorithm, equivalence of Hall and
Konig-Egervary theorems, matchings in general graphs. Relevant book sections:
25,27.
Wednesday 6/23: Distributed handout on topics
covered Tuesday. Returned HW #3 and discussed solutions. Topics covered:
matchings in bipartite graphs, Hall's theorem, vertex covers. Relevant book
sections: 25.
Tuesday 6/22: Distributed HW #4 and collected HW #3.
Topics covered: list colorings, basic bounds, the List Coloring Conjecture,
chromatic number vs. clique number, Mycielski graphs, introduction to
perfect graphs.
Monday 6/21: Returned midterm exam. Topics covered: application of graph
coloring to channel assignment, edge colorings, Vizing's theorem, Konig's
theorem, introduction to list colorings. Relevant book sections: 20.
Thursday 6/17: Midterm exam.
Wednesday 6/16: Returned HW #2. Finished proof of Brooks' theorem. Discussed
solutions to review problems and problems on HW #2.
Tuesday 6/15: Distributed HW #3 and collected HW #2.
Topics covered: chromatic number, coloring algorithms, bounds on chromatic
number, six- and five-color theorems for planar graphs, connection to map
coloring; started proof of Brooks' theorem. Relevant book sections:
17,18,19.
Monday 6/14: Distributed review problems for midterm exam. Midterm exam will
consist of three sections: definitions and statements of theorems,
applications to example graphs, and proof-type problems. The material
covered on the exam includes that in sections 1-15 of the book, plus the
additional handouts. Topics covered in class today: genus of graphs,
geometric and abstract duals; basic definitions for graph coloring and
connection to the four-color map theorem. Relevant book sections: 14,15,17.
Thursday 6/10: Distributed handout on
definitions related to Matrix-Tree Theorem and planarity. Topics covered:
more on Kuratowski's Theorem, minors vs. topological minors, Euler's formula
and its corollaries, thickness. Relevant book sections: 12,13.
Wednesday 6/9: Returned HW #1. Topics covered: adjacency and incidence
matrices, the Matrix-Tree Theorem, planarity, homeomorphic graphs,
Kuratowski's Theorem. Relevant book sections: 2,10,12.
Tuesday 6/8: Collected HW #1 and distributed HW #2.
Topics covered: cycle rank and cutset rank, enumerating spanning trees,
Cayley's theorem, Prufer codes, graceful labellings; basic definition and
characterization of bipartite graphs. Relevant book sections: 3,5,9,10.
Monday 6/7: Distributed handout on Chvatal's
theorem. Topics covered: definitions of tree and subgraph, characterizations of
trees, spanning trees, Kruskal's (greedy) algorithm for minimum-cost
spanning trees. Relevant book sections: 9,11.
Thursday 6/3: Topics covered: Degree sequences, regular graphs, Ore's theorem,
Chvatal's theorem, the traveling salesman problem, isomorphism. Relevant book
sections: 3,5,7,8.
Wednesday 6/2: Distributed handout on
alternative proof of characterization of Eulerian graphs. Topics covered:
more on connectivity, bridges and cutvertices, Fleury's algorithm,
Hamiltonian cycles (basic definitions, Dirac's theorem). Relevant book
sections: 3,5,6,7.
Tuesday 6/1: First day of class; syllabus, questionnaire, and HW #1 handed
out. The syllabus contains an important error: the class meets in Hill 552,
not Hill 525. Topics covered: basic definitions, Euler trails,
connectivity; relevant book sections: 2,5,6. Added reference to advanced
paper on enumerating Euler trails to information page.
|
|