10.30-11.15: Paul Seymour Princeton University, Princeton, NJ, USA
Perfect matchings in planar cubic graphs.
A well-known conjecture of Lovász and Plummer from the
1970's asserts that for every 2-edge-connected cubic graph G with n
vertices, the number of perfect matchings in G is exponential in n.
This seems to be wide open still, and as far as we know the best lower
bound is n/2 + 1.
In this talk we sketch a proof of the Lovász-Plummer conjecture
for PLANAR cubic graphs. In this case the problem is more tractable,
because we can use the four-colour theorem as a source of
3-edge-colourings and hence of perfect matchings.
This is joint work with Maria Chudnovsky, Columbia University.
11.15-12.00: Jim Geelen University of Waterloo, Waterloo, Ontario, Canada
In joint work with Bert Gerards and Geoff Whittle, we hope to
extend the Graph Minors Project of Neil Robertson and Paul Seymour
to matroids representable over a fixed finite field. In this talk
we discuss the motivation for the project and report on our progress.
13.30-14.15: Robin Thomas Georgia Institute of Technology, Atlanta, GA, USA
Kt minors in large t-connected graphs.
A graph G has a Kt minor if a graph isomorphic to Kt, the
complete graph on t vertices, can be obtained from a subgraph
of G by contracting edges. Jorgensen conjectured that every
6-connected graph with no K6 minor has a vertex whose deletion
makes the graph planar. This is of interest, because it implies
Hadwiger's conjecture for graphs with no K6 minor (which is
known to be true, but Jorgensen's conjecture would give more
I conjecture that for every integer t there exists an integer N
such that every t-connected graph on at least N vertices with no
Kt minor has a set of at most t-5 vertices whose deletion makes
the graph planar. If true, this would be best possible in the sense
that neither t-connectivity nor the size of the deleted set can
be lowered, and for t>7 some lower bound on the number of vertices
is needed. Furthermore, no graph satisfying the conclusion of the
conjecture has a Kt minor.
A couple of years ago we proved the conjecture for t=6 in joint work
with Matt DeVos, Rajneesh Hegde, Kenichi Kawarabayashi, Sergey Norin
and Paul Wollan. Thus Jorgensen's conjecture holds for sufficiently
big graphs. In the talk I will report on recent progress for t>6
obtained in joint work with Sergey Norin.
14.15-15.00: Carsten Thomassen Danmarks Tekniske Universitet, Lyngby, Denmark
János Barát and I made the following conjecture: For every tree T,
there is a natural number kT such that every
graph of size divisible by |E(T)| has an edge-decomposition into
subgraphs each isomorphic to T. The conjecture is trivial when T
has at most two edges. When we made the conjecture we could not prove it
for one single tree with three or more edges. However, we showed that
the conjecture holds for the claw (the star with three edges) provided
Tutte's 3-flow conjecture is true. A year ago I verified the
conjecture for one tree. Recently, I have verified it for a second tree.