Math 510: Introduction to Graph Theory
Spring 2012

The course is for students in the second year and higher; it is not an introductory graduate course. The absolute minimum requirement is a good understanding of abstraction and a solid modern algebra background (as from a graduate course), and the more graduate math you know, the better (that's the famous "mathematical maturity"). If you aren't sure whether you might be interested or ready for this class, please see me.

Textbook

Graph Theory by Reinhard Diestel, fourth edition (Springer-Verlag, 2010). The text can be read on line; there are also the table of contents, a cheap student PDF, etc.

We will cover as many chapters as we can, which is possibly about six to eight.

Combinatorics Seminar

The Combinatorics Seminar meets on Tuesdays at 1:15 in LN-2205. (Occasionally at a different time; check the schedule.) All 510 students are invited to attend (if the room is big enough for 510 students—Sorry, bad old joke, slap).

Supplementary Mathematics

• Synonym lists:
  • Cycle, circuit, circle, polygon. These are names for a (nonempty) connected edge set with all degrees equal to 0 or 2 (this is what the book would call a "cycle").
• The oriented incidence matrix is the V × E matrix H(G) in which the column corresponding to edge e has one +1 and one −1 in the rows corresponding to the endpoints of e, with 0's elsewhere. (We rarely have to worry about the choice of which endpoint gets which sign; we can just make an arbitrary choice and stick to it.) This definition works for multigraphs without loops. The matrix defined in the book, with only +1's, is the unoriented incidence matrix.
• An algebraic cycle of G over F (where F is a field) is an element of the cycle space of G over F, which is defined to be the null space Nul H(G) (also called Z₁(G; F), especially in algebraic topology). An (algebraic) cocycle is an element of the cocycle space, which is defined to be the orthogonal complement of the cycle space, i.e., it is the row space Row H(G). A binary cycle or cocycle is an algebraic cycle with F = F₂, or equivalently the corresponding subset of E.
• A signed graph is a graph whose edges are labelled positive or negative. Thus, it is Σ = (G, σ) where σ: E → {+,−}.
  • A subgraph is balanced if every circuit in it is positive. If all the signs are negative, a balanced subgraph is a bipartite subgraph. If all signs are positive, a balanced subgraph is any subgraph.
  • Switching a vertex set X in a signed graph means reversing the sign of every edge that has one endpoint in X and the other in V \ X. Switching X is equivalent to switching each vertex in X separately (in any order).
  • Coloring a signed graph is done with signed colors. For a signed k-coloring, the color set is C_k = {0, ±1, ±2, ..., ±k}. For a zero-free k-coloring, the color set is C_k \ {0}. A coloring γ is proper if, for each edge e_vw, we have
    γ(v) ≠ σ(e_vw)γ(w). The chromatic polynomial χ_Σ(2k+1) is defined, for k = 1, 2, ..., to be the number of proper signed k-colorings. The number that are zero-free, written χ_Σ*(2k), gives the zero-free chromatic polynomial.
• The "parts" of a tree decomposition: I prefer a more distinctive name: nodal set for V_t and "nodal subgraph" for G[V_t]. (I use the term "node" for a vertex of T. Generally, "node" is a synonym for "vertex" but not used much any more.)

To my home page.