ABSTRACTS

Combinatorial Potlatch

November 8, 2003
UVic Downtown Campus
910 Government Street


10:00 - 10:50

Steph van Wilgenburg
UBC

Enumerative properties of Ferrers graphs

For every Ferrers diagram one can construct a bipartite
graph in a natural way. In this talk we introduce these graphs
and calculate the number of spanning trees, the number of Hamiltonian
paths, and the chromatic polynomial of such a graph. In particular,
it transpires that formulas for the former two have simple combinatorial
descriptions, while the latter is related to a set of permutations
that satisfy certain criteria.

This is joint work with Richard Ehrenborg.

11:20 - 12:10

Peter Horak
University of Washington

Graph Theory as an Integral Part of Mathematics

Nobody doubts the significance of the applications of graph theory to 
other sciences (e.g. electrical engineering, psychology, economics) or 
to real life problems. However, in this talk, we concentrate on a different 
type of applications.  Namely, the possibility of the utilization of graph 
theory methods in other branches of mathematics. To demonstrate this 
kind of application, graph theoretical proofs of well-known theorems in 
set theory, number theory, analysis, etc.will be presented.

14:00 - 14:50

Rick Brewster
University College of the Cariboo

Categorical aspects of graph homomorphisms

Given graphs G and H, a homomorphism of G to H,
written G -> H, is a function f: V(G) -> V(H) such that xy in E(G) 
implies f(x) f(y) in E(H).  The class of finite graphs together 
with graph homomorphisms is the category Graph.

In this talk we will explore the rich structure of Graph,
with a particular focus on density theorems, and their
connection to duality theorems.  Algorithmic and complexity
issues will also be discussed.

15:20 - 16:10 

Zdenek Ryjacek
University of Western Bohemia 
Czech Republic

Closure concepts, contractible subgraphs and hamiltonian 
properties of line graphs.

The contractibility technique was developed recently as an extension of
the well-known Catlin's reduction technique for hamiltonian properties
of line graphs (it turns out that - roughly speaking - a graph F is
contractible if and only if the circumference of L(G) equals the
circumference of L(G|F) for any graph G containing F). The
technique yields a new powerful closure concept for line graphs and
could be a potential tool for attacking some long-standing open
problems, e.g. the dominating cycle conjecture (every essentially
4-edge-connected cubic graph G has a cycle C such that G-C is
edgeless).