There are three parts to the course. This page has the list of what we cover (partial, at this time; it will develop as we go).
"Study" means you should learn this well so you can use it later. "Read" means it's worth knowing but not in detail.
Abbreviations:
The textbook for this is Reinhard Diestel, Graph Theory, 3rd edition, Springer, 2005. We study the most basic parts of the book.
| Section | Study | Read | Omit | Notes |
|---|---|---|---|---|
| Chapter 1 Basics |
All, except: | Th 1.3.4, Cor 1.3.5; §1.10 |
Th 1.4.3, Lem 1.5.5, proof of Pr 1.5.6 |
A bit of almost everything (almost). |
| Chapter 3 Connectivity |
§§3.1, 3.3 | §3.2 to Th 3.2.2 | Third proof of Menger: p. 63 bottom to p. 66 middle | Fundamental for graph investigations. |
| Chapter 4 Planarity |
§§4.2, 4.4-6 | §§4.1, 4.3 | Lem 4.2.2 proof; Pr 4.2.8 proof; §§4.3, 4.5, 4.6 all proofs; §4.4 pp. 99-100 |
A huge part of graph theory. |
| Chapter 5 Coloring |
§§5.1-3, except: | Pr 5.2.2, Cor 5.2.3; p. 116 bottom to Th 5.2.5; chapter notes |
§5.2 after Th 5.2.5; §5.3 after statement of Th 5.3.2 |
A huge part of graph theory. |
| Chapter 6 Flows |
§§6.1-3 | §6.4; Th 6.5.3 statement. Suggested: §6.6 Conject's, Th |
Proofs in §§6.2, 6.4-6 | Kinds of "flow": circulation, source-sink, nowhere-zero; integral, real, group-valued. |
| Chapter 10 Hamiltonicity |
§10.1; Ore's Th |
P. 277 to end of section |
Scratching the surface of a complex topic. |
There is no textbook for this. I will lecture and find papers to use, specifically two of mine:
The textbook for this is Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer, 2001. We'll study graph automorphism groups and graph matrices, emphasizing the latter.
This part of the syllabus is under development and will be adjusted as we go along.
| Section | Study | Read | Omit | Notes |
|---|---|---|---|---|
| Chapter 1 Graphs |
All | — | — | Some parts are new, such as homomorphisms, Johnson graphs, and some about line graphs. |
| Chapter 2 Groups |
All, except: | §2.6 | §2.3 | "Read" means in particular you don't have to learn the proofs. |
| Chapter 3 Transitive Graphs |
§§3.1-4 | §3.7 | ||
| Chapter 4 Arc-Transitive Graphs |
§§4.1, 4.5 | §§4.3, 4.4 | §4.3 proofs and lemmas | |
| Chapter 8 Matrix Theory |
§§8.1-6, 8.8; Cor 8.9.2; §8.12 |
§8.10 | §8.10 proofs | Note Perron-Frobenius Thm 8.8.1 and application to real symmetric matrices, especially adjacency matrices. |
| Chapter 9 Interlacing |
§9.1 | |||
| Chapter 10 Strongly Regular Graphs |
§§10.1-3, 10.5 | |||
| Chapter 11 Two-Graphs |
§§11.1-2, 5-6 | §11.3 | We treat two-graphs as switching classes of signed complete graphs. | |
| Chapter 12 Line Graphs and Eigenvalues |
§§12.1-3, 12.7-8 L.g. of s.g. |
§12.4 | With line graphs of signed graphs. | |
| Chapter 13 The Laplacian of a Graph |
§13.1 | With signed graphs. |