|
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). |