Graph Minors

How to contact me.

Deletions and Contractions

Let G=(V,E,I) be a graph and e be an edge of G. We write G-e for the subgraph of G with vertex set V(G) and edge set E(G)-{e}. Then, G-e is the subgraph that results from deleting edge e from G. We write G.e for the graph which results from contracting the edge e. Note that G.e will not usually be a subgraph of G. If G is a simple graph (no loops, no multiple edges), then G-e must be simple, but G.e may have loops or multiple edges. For some applications of graph minors, it may be possible to avoid using loops and multiple edges, for others loops and multiple edges will be necessary.

Minors

A minor of G is a graph that results from a sequence of edge deletions and contractions.

Colourings

A k-colouring of a graph G is a function f:V(G)->{1,2,...,k}, such that no edge e=(u,v) has f(u)=f(v). If a graph G contains a loop, then G has no k-colouring for any k. A graph which has a k-colouring is called k-colourable. The chromatic number of a graph G is the minimum integer k such that G has a k-colouring. For example, G is bipartite if and only if G is 2-colourable.

Similarly, a k-edge-colouring of a graph G is a function g:E(G)->{1,2,...,k}, such that no pair of incident edges, e and f have g(e)=g(f). The edge chromatic number of a graph G is the minimum integer k such that G has a k-edge-colouring.

A k-total-colouring of a graph G is a function h from the union of E(G) and V(G) to {1,2,...,k}, such that no pair of incident elements, e and f have h(e)=h(f). The total chromatic number of a graph G is the minimum integer k such that G has a k-total-colouring.

Heuristics for Colouring

Sometimes it is only necessary to find a colouring that does not use "too many" colours, as opposed to finding a colouring that is best possible. A heuristic is a method of determining an approximate solution, rather than an exact solution.

For example, a heuristic for vertex colouring might be: colour a vertex of minimum degree last. That is, pick out a vertex of minimum degree, colour the remaining vertices, and then replace the vertex, assigning it one of the colours not used among its neighbours. Such a colouring uses at most D+1 colours if the graph has maximum degree D.

Thus, for example, all planar graphs are 6-colourable, since every planar graph must have a vertex of degree at most five. A little bit of extra work shows that the five neighbours of a vertex of degree five cannot all be adjacent. It is easy to contract two non-adjacent neighbours (into a new vertex), retaining planarity. Thus, every planar graph is 5-colourable.

About 140 years after de Morgan popularized the four colour conjecture,
Haken and Appel proved the four colour theorem for planar graphs.

Chromatic Polynomials

Let P(G,k) denote the number of k-colourings of the graph G, where k is a positive integer. Let e be an edge of G. It is an easy exercise to show that P(G,k)=P(G-e,k)-P(G.e,k). (The reader can see that multiple edges carry no extra information over that carried by an edge of multiplicity one.) A simple induction proof now demonstrates that P(G,k) is a polynomial in k with integer coefficients (that alternate in sign).

Other Polynomials

For a graph G, possibly containing loops and multiple edges, we define the
Tutte Polynomial T(G;x,y) and the Rank Polynomial R(G;x,y) by the following properties:

R(G;x,y)=(1+y)R(G-e;x,y) if e is a loop,
R(G;x,y)=(1+x)R(G.e;x,y) if e is a cut edge,
R(G;x,y)=R(G-e;x,y)+R(G.e;x,y) otherwise; and
R(G;x,y)=1 if G has no edges;

T(G;x,y)=yT(G-e;x,y) if e is a loop,
T(G;x,y)=xT(G.e;x,y) if e is a cut edge,
T(G;x,y)=T(G-e;x,y)+T(G.e;x,y) otherwise,
T(G;x,y)=1 if G has no edges.

It may not be obvious from these definitions that T(G;x,y) and R(G;x,y) are well defined, but it is readily apparent that if they are well defined, then T(G;x,y) and R(G;x,y) are polynomials in x and y with non-negative coefficients. Let r[i,j] denote the number of edge induced subgraphs of G with rank i and corank j. The matrix (r[i,j]) is called the rank matrix. Another version of the rank polynomial is given by setting R'(G;x,y) to be the sum of the terms a[i,j]xiyj. This is related to the rank polynomial we presented by R(G;x,y)=R'(G;1/x,y)xrank(G). It is a routine inductive exercise to show that these definitions of R(G;x,y) agree (if I have typeset them correctly).
A few examples of the Tutte Polynomial.

The flow polynomial, the chromatic polynomial, the number of spanning trees, and many other peices of information can be deduced from the Tutte polynomial (if one knows the number of vertices). The Rank polynomial and Tutte polynomial contain the same information, since R(G;x,y)=T(G;1+x,1+y), but the Tutte polynomial might be expected to have smaller coefficients.

Any two trees (or forests) with k edges have the same Tutte polynomial, xk.

The two nonisomorphic graphs with adjacency matrices
0  -2  -1   0   0   0          0  -2  -1   0  -1  -1
-2   0  -1  -1   0  -1         -2   0  -1  -1   0   0
-1  -1   0  -1  -1   0         -1  -1   0  -1   0   0
0  -1  -1   0   0  -1          0  -1  -1   0   0  -1
0   0  -1   0   0  -1         -1   0   0   0   0  -1
0  -1   0  -1  -1   0         -1   0   0  -1  -1   0
have the same Tutte polynomials.

The number of spanning trees of a connected graph G is T(G;1,1).

The number of maximal forests of a graph G is T(G;1,1).

The number of acyclic subgraphs (forests) of a graph G is T(G;2,1).

The number of spanning edge induced subgraphs of a graph G is T(G;1,2).

T(G;2,2)= 2|E(G)|.

T(G;0,0)=0, if G has an edge.

The chromatic polynomial of a connected graph G on n vertices is
(-1)n-1 k T(G;1-k,0).

The flow polynomial: Let F(G;k) denote the number of nowhere zero mod k flows of the graph G. Then, for a connected graph G on n vertices and m edges,
F(G;k)=(-1)m-n+1 k T(G;0,1-k).

The Tutte Polynomial is a reconstructible parameter. That is, given the collection of vertex deleted subgraphs of G, but not G itself, it is always possible to calculate T(G;x,y).
Note: I have chosen a form of the Rank polynomial that ignores the number of vertices. This allows a straightforward generalization to matroids - just change cut edge to coloop.

Even R' ignores isolated vertices.

The join, Ú H of two graphs G and H is the graph with V(G Ú H) = V(G) È V(H) and E(G Ú H) = E(G) È E(H)  È  {vw : v Î V(G), w Î V(H) }.

For a positive integer k, we use λ(k) to mean λ(λ-1)...(λ-k+1).

Suppose that the chromatic polynomial of G is anλ(n) + an-1λ(n-1) + ... +a1λ(1) and that the chromatic polynomial of H is bmλ(m) + bm-1λ(m-1) + ... +b1λ(1).

Then, the chromatic polynomial of Ú H is the sum of all of the terms of the form aibjλ(i+j).

(The proof is left as an exercise using the formula P(G,k)=P(G+e,k)+P(G.e,k), where e is an edge in the complement of G.)

Last modified March 15, 2009, by S.C. Locke.