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.
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.
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.
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.
Last modified April 29, 1996, by S.C. Locke.