MATH 582

STRUCTURE OF GRAPHS, Spring 2005

Summary of Lectures

This page contains a summary of the lectures in this course for Spring 2005. It lists only the topics discussed in each lecture. The text provides extensive discussion and additional material, so no additional notes are given here.


1 1/19We: introduction (overview of topics)

Chapter 6: Elementary Structural Concepts
2 1/21Fr: Matrix Tree Theorem, Matrix Arborescence Theorem, counting Eulerian circuits
3 1/24Mo: graceful labelings (hypercubes), T-decomposition (girth vs diameter)
4 1/26We: graph packing (Sauer-Spencer Thm, Bollobas-Eldridge Conj), graphic lists
5 1/28Fr: Aigner-Triesch for bigraphic lists, potentially k-edge-connected lists, vertex ptn for maximum degree
6 1/31Mo: vertex partition for minimum degree (Stiebitz), graph reconstruction through Counting Theorem
7 2/02We: reconstruction of trees and almost all graphs, edge-reconstruction
8 2/04Fr: isometric embedding & metric representation
9 2/07Mo: product dimension

Chapter 7: Connection and Cycles
10 2/09We: Edmonds' Branching Theorem and applications
11 2/11Fr: Lucchesi-Younger Theorem
12 2/14Mo: k-linked graphs, forced subdivisions
13 2/16We: ear decomposition, contraction lemma, 3-connected graphs, Halin example
14 2/18Fr: minimally k-connected graphs (Mader etc.), sketch of Gyori-Lovasz Theorem
15 2/21Mo: Nash-Williams Orientation Theorem
16 2/23We: toughness (9/4-tough non-Hamiltonian), k-closure, density theorems
17 2/25Fr: Bondy-Chvatal condition for t dominating verts, Las Vergnas condition, Lu's Theorem strengthening Chvatal-Erdos (skipping hard case)
18 2/28Mo: Oberly-Sumner Theorem, Ryjacek closure (sketch), Erdos-Gallai extremal result on circumference
19 3/02We: Bondy's Lemma on long paths, Fan's Theorem, Ghoula-Houri's Theorem
20 3/04Fr: Meyniel's Theorem (Bondy-Thomassen proof), gossip problem

Chapter 8: Planar and non-planar graphs
21 3/07Mo: MacLane/Whitney planarity criteria, Schnyder labelings and grid embeddings
22 3/09We: Schnyder labelings (proofs)
23 3/11Fr: graph dimension, lemmas for Lipton-Tarjan Separator Theorem
24 3/14Mo: Lipton-Tarjan Separator Theorem, applications to independent sets and pebbling
25 3/16We: Thomassen 3-colorability of planar graphs with girth at least 5
26 3/18Fr: Grotzsch's Theorem, Wernicke by discharging, reducibility of Birkhoff diamond, Tait's Theorem
27 3/28Mo: interval number and total interval number of planar graphs
28 3/30We: thickness and pagenumber
29 4/01Fr: crossing number and application
30 4/04Mo: t-linear crossing numbers, genus, Heawood's Formula
31 4/06We: voltage graphs

Chapter 9: Graph minors and related topics
32 4/08Fr: graph minors, testing minors, K4-minor-free = 2-decomposable
33 4/11Mo: treewidth, cops-and-robber
34 4/13We: brambles, min/max for treewidth
35 4/15Fr: graph minor approach, well-quasi-ordering for trees (sketch)
36 4/18Mo: cycle covers and flows
37 4/20We: 8-flow theorem
38 4/22Fr: modular flows, 6-flow theorem
39 4/25Mo: snarks and faithful covers

Chapter 10: Algebraic graph theory
40 4/27We: eigenvalues (up to bipartite graphs)
41 4/29Fr: eigenvalues of regular graphs
42 5/02Mo: strongly regular graphs (Friendship Theorem), Laplacian eigvals
43 5/04Mo: chromatic polynomial, rank polynomial