CHROMATIC GRAPH THEORY
GRAPH THEORY SEMINAR
SCHEDULE (Fall 2007)
Tuesday 2:00-2:50 pm, Alavi
- November 27
The Fundamental Group of a Graph
The fundamental group is a much
studied topic in elementary topology.
As graphs are also topological spaces,
we shall investigate the fundamental group
structure of an arbitrary graph G.
In particular, the fundamental group of a graph
is a free group. We shall also discuss some
connections between the fundamental group of
a graph and the genus of the graph.
- November 13
Cages and Cayley Graphs
A (k,g)-cage is a regular graph of valence k
and girth g with vertex set of least order. A Cayley
graph is a graph which has a regular group of automorphisms.
In this talk, we will discuss the following result:
(##) (Alain Bretto and Luc Gillibert)
For p a prime number greater or equal to 5, we have a
regular graph of degree p, of girth 6, and with an order equal to 2xp2.
Hence if G is a c(p,6)-cage, the order of V is bounded by 2xp2.
- November 6
- October 30
The 4-color Problem, A Look Back
The 4-color Problem, A Look Back.
- October 23
A Four Colorings Theorem
The most famous and most studied graph coloring number is the
chromatic number. If the chromatic number of a graph G is k,
then each k-coloring of G has three properties that give rise
to three additional colorings of G. Relationships among these four
colorings are studied.
- October 16
T-colorings and the Channel Assignment Problem
The Channel Assignment Problem
is the problem of how to assign channels
to transmitters that interfere with each other in some way.
This situation can be modeled uning graph theory, with
edges reperesenting the interference between transmitters.
T-coloring can be used to address this problem.
We will determine the minimum number of channels required,
and how this relates to proper colorings.
We will also address the question of how large the
range of the channels used must be.
- October 2
Using Eigenvalues to Search for Regular Graphs of Girth 5
Hoffman and Singleton identified those values of r
for which there can exist an r-regular graph of girth
5 and order r2 + 1, namely r = 2, 3, 7, and possibly 57.
Possibly 57? What does that mean? Will Brown showed that
there are no r-regular graphs of girth 5 and order r2 + 2.
We consider r-regular graphs of girth 5 and order r2 + 3.
Using eigenvalue methods and Maple to factor large polynomials,
we show the nonexistence of such graphs for r between 5 and 11 (inclusive).
Similarly, no r-regular graphs of girth 7 and order r3 - r2 + r + 1 exist.
On the other side, we give a simple construction for the Robertson graph
of order 19 with r = 4, some graphs with order
20 and r = 4, and for two graphs of order 12 with r = 3.
- September 25,
Fundamentals of Eigenvalues and Graphs
What kind of eigenvalues does a connected graph have?
What do eigenvectors look like?
What kind of basis do we get?
What is the Raleigh Quotient?
What do the largest and smallest eigenvalues tell us?
When is the average degree an eigenvalue? The maximum degree?
In a connected graph, why is the largest eigenvalue always simple?
What are the eigenvalues of complete graphs,
complete graphs, cycle, and paths?
- September 18,
The Garden of Eden Problem
Let G and H be graphs.
We define the "offspring" product to be the graph
obtained by orienting H and then replacing each
arc with a copy of G, in a specified manner.
This produces a new graph, which has an obvious edge
composition into copies of G. The main issues to be
addressed concern whether or not this obvious
decomposition is unique. We shall discuss various
results towards this end, as well
as a connection to a certain NP completeness problem.
- September 11,
A. T. White:
Starting wih a simple observation about one conventional die,
we (David Craft and I) extend to the three cubic dice based upon the
platonic solids and then to cubic maps in general. We take special
interest when a 3-region coloring exists, for then 3's abound: we find a
3-edge coloring of a special sort, and also three partitions of the
vertex set of the cubic graph which lead to various topological