


Graphs and Matroids / Graphes et matroîdes Org: Luis Goddyn (Simon Fraser) and/et Ladislav Stacho (Simon Fraser)
 KATHIE CAMERON, Wilfrid Laurier University, Waterloo, Ontario N2L 3C5
Finding induced matchings and dissociation sets in graphs

A matching M in a graph G is a subset of the edges of G such that
each vertex of G is met by at most one edge of M. An induced
matching in a graph G is a matching M such that no pair of edges of
M is joined by an edge of G; that is, an induced matching is a
matching which forms an induced subgraph of G. We can think of an
induced matching as a set of edges which induces a subgraph where all
vertex degrees are 1.
A dissociation set is a set of vertices which induces a subgraph where
all degrees are 0 or 1.
We consider the problems of finding a largest induced matching and a
largest dissociation set.
As is typical in the field of graph algorithms, we show these problems
to be hard in certain classes and easy in others.
 DALIBOR FRONCEK, University of Minnesota Duluth, USA
Factorizations of complete graphs into spanning trees

Although the factorization of complete graphs into isomorphic spanning
trees is a very natural problem, it has not received much attention.
One reason may be that the labeling methods that are often used for
isomorphic decompositions of complete graphs K_{2n+1} into 2n+1
copies of trees with n+1 vertices (like graceful labeling) do not
work for factorizations unless they are modified. Such a modification
is not hard to discover, as we show in this talk when we define a
blanded labeling and its generalizations. However, it is much harder
to prove the existence of a blended labeling even for very simple
classes of trees. For instance, it is well known that all caterpillars
are graceful. On the other hand, it is still not completely known which
caterpillars of diameter 5 admit a blended labeling.
We proved recently that a complete graph K_{4k+2} can be factorized
into isomorphic trees with any diameter d where 3 £ d £ 4k+1.
We will show that for each K_{4k}, where k ¹ 2^{q}, there also
exists an isomorpic factorization into trees with any diameter d
where 3 £ d £ 4k1. Partial results for k=2^{q} will be also
mentioned. If time permits, we will present the complete
characterization of caterpillars of diameter 4 that factorize
complete graphs K_{4k+2} and some related results.
 PENNY HAXELL, University of Waterloo, Waterloo, Ontario
Independent transversals in rpartite graphs

An independent transversal in an rpartite graph G is an
independent set in G consisting of exactly one vertex from each
partite class. For arbitrary positive integers n and r we
determine the largest integer D = D(r,n), for which any
rpartite graph with partite sets of size n and of maximum degree
less than D has an independent transversal. This value was
known for all even r. Here we determine the value for odd r and
find that D(r,n)=D(r1,n). Informally this means that the
addition of an oddth partite set does not make it any harder to
guarantee an independent transversal.
This talk represents joint work with Tibor Szabó.
 PETER HORAK, University of Wasington, Tacoma, Washington, USA
Covering vertices of a graph by trees

Several ways have been introduced to measure how far a graph G is
from having a hamiltonian cycle/path. In this talk we deal with two of
them that involve trees.
On one hand, one can understand a hamiltonian path as a spanning tree
with the maximum degree two. Then it is natural to ask what is the
smallest number k so that there is in G a spanning tree of the
maximum degree k. Win showed that k £ é[(G1)/(d)]ù, where d stands for the minimum
degree of G. There are many variations, extensions and
generalizations of the result.
On the other hand, it is possible to see a hamiltonian path as a
spanning forest. Then, to measure how far is G from a hamiltonian
graph, one asks what is the minimum number m of paths covering all
vertices of G. In a classical paper og Gallai and Milgram it is shown
that m is at most the independence number of G. Also in this case
there are many papers dealing with the topic, mostly with the
complexity aspects of the problem.
To get a deeper insight into the problem we discuss the following
common generalization of the above two approaches. Let G be a graph
and k be a natural number. Determine the smallest number m so that
there are disjoint trees T_{1},...,T_{m}, each of them of maximum
degree at most k, covering the vertices of G.
 JING HUANG, Department of Mathematics and Statistics, University of Victoria,
Victoria, British Columbia V8W 3P4
Bigraphs of Ferrers dimension two and circular arc graphs

In this talk, I will describe relations among interval digraphs,
interval containment digraphs, interval bigraphs, bigraphs of Ferrers
dimension two, and circular arc graphs of clique covering number two.
 GARY MCGILLIVRAY, University of Victoria, Victoria, British Columbia
NearUnanimity functions of reflexive graphs

We report on joint work with Richard C. Brewster, Tomas Feder, Pavol
Hell and Jing Huang.
Let H be a graph and k ³ 3. A nearunanimity function of
arity k is a homomorphism g from the kfold Cartesian product
H^{k} to H such that g(x_{1}, x_{2}, ..., x_{k}) = a whenever at least
k1 of the x_{i}'s equal a. These can be viewed as an algorithmic
tool in the following sense: Feder and Vardi [SIAM J. Computing, 1998]
proved that if a graph H admits a nearunanimity function, then the
homomorphism extension problem for (equivalently, retraction to) H is
polynomialy solvable. It is therefore of interest to determine which
graphs admit a nearunanimity function.
We focus on reflexive graphs. It is proved that every reflexive
chordal graph admits a nearunanimity function, and several bounds for
the arity of these functions are given. In particular, every
reflexive chordal graph with n vertices has a nearunanimity function
of arity at most n Ön + 1. We also exhibit nonchordal graphs
which admit nearunanimity functions. Forbidden substructures for
reflexive graphs that admit a nearunanimity function are then
investigated. It follows from our results that, for instance, that no
reflexive cycle of length at least four admits a nearunanimity
function of any arity.
 SEAN MCGUINNESS, Adelphi University, Garden City, New York, USA
Sequential transversals in matroids

Let S be a finite set and S be a collection of subsets of
S. For each x Î S let S_{x} = {T Î S  x Î T }. Suppose we choose elements x_{1}, ...,x_{n} in such a way that we first choose x_{1} belonging to some subset
of S_{x1}. For i=2, ...,n we choose x_{i} Î S_{xi} \S_{x1} È¼ÈS_{xi1}. We call the set { x_{1}, ... ,x_{n} } a
sequential transversal of S, and we let
T_{S} be the set of all sequential transversals
of S, which includes Æ as well. We examine
conditions under which the pair (T_{S},S) is
matroid. It is shown that every matroid on a set S can be defined as
pair (T_{S},S) where T_{S}
is orderindependent; that is, the elements in any sequential
transversal can be picked in any order. For S Í 2^{S}, various conditions and examples are provided in which
(T_{S}, S) is a matroid. We also provide a
counterexample to a conjecture of Jones.
 JENNY MCNULTY, The University of Montana
Nonorientable matroids and characteristic sets

The characteristic set c(M) of a matroid, M, is the set of
primes p and possibly 0, so that k Î c(M) if and only if M
is representable over a field of characteristic k. Much work was
done to classify characteristic sets and to construct rank 3
matroids, M, with c(M)=c for each possible characteristic
set c. We investigate several classes of rank 3 sequentially
unique matroids, M, with c(M)=p, such as the Reid matroids. We
show these classes are not orientable. Lastly, we discuss several open
problems relating orientability and characteristic sets.
 WENDY MYRVOLD, Department of Computer Science, University of Victoria
Hunting for torus obstructions

A torus is a surface shaped like a doughnut. A graph is
toroidal if it embeds on the torus with no crossing edges. A
topological obstruction for the torus is a graph G with minimum
degree three that is not embeddable on the torus but for all edges e,
Ge embeds on the torus. A minor order obstruction has the
additional property that for all edges e, G contract e embeds on
the torus.
The aim of our research is to find all the obstructions to the torus
(both minor order and topological). To date, we have found 239,322
topological obstructions and 16,629 minor order obstructions.
Previously, only a few thousand had been determined. This talk
discusses the techniques used to find these obstructions and suggests
avenues for completing this research.
 NANCY NEUDAUER, Pacific University, Forest Grove, Oregon
Graph representations of a bicircular matroid

Let G be a graph (loops and parallel edges allowed) with vertex set
V={1,2,¼,n} and edge set E. In the classical matroid
associated with a graph, a set of edges is independent in the matroid
if it contains no cycles, and the circuits of the matroid are the
single cycles of G. The bicircular matroid of G is the
matroid B(G) defined on E whose circuits are the subgraphs which
are subdivisions of one of the graphs: (i) two loops on the same
vertex, (ii) two loops joined by an edge, (iii) three edges joining
the same pair of vertices.
The bicircular matroid is known to be a transversal matroid and thus
can be represented by a family of sets, called a presentation.
Given a transversal matroid, we can determine whether it is
bicircular. I will show that, given any presentation of a bicircular
matroid, we can find a graph representing the matroid, and that, in
some cases, there is more than one graph. We investigate how the
graphs representing a bicircular matroid are related, and what this
means in terms of their presentations as transversal matroids.
 ORTRUD OELLERMANN, University of Winnipeg, Winnipeg, Manitoba
Contour vertices and convexity notions in graphs

The interval between a pair u,v of vertices in a graph G is the
collection of all vertices that belong to some shortest uv path in
G. A set S of vertices is convex if it contains the interval
between all pairs of vertices in S. The convex hull of a set S of
vertices in a graph G is the smallest convex set that contains S.
A vertex v of a graph G is a contour vertex of a set S if its
eccentricity, ecc(v)=max{d(v,u)  u Î V(G)}, is at least as
large as that of its neighbors in S. We show, for any connected
graph G and any convex set S of G, that S is the convex hull of
the contour vertices of S. The closure of a set S of vertices of a
graph is the union of intervals between pairs of vertices of S taken
over all pairs of vertices of S. A set S of vertices of G is a
geodetic set if its closure is V(G). The smallest cardinality of a
geodetic set for a graph G is called the geodetic number of
G. We show that in general the problem of finding the geodetic
number of a graph is NPhard. For distance hereditary graphs it is
shown that the contour vertices form a geodetic set. The Steiner
interval of a set S of vertices in a graph is the union of all
vertices that belong to some Steiner tree for S (i.e., a tree
of smallest size that contains S). A set S of vertices in a graph
G is a Steiner geodetic set if its Steiner interval is V(G). The
smallest cardinality of such a set is the Steiner geodetic number of
the graph. We compare the geodetic and the Steiner geodetic number of
a graph and show how contour vertices can be used to find the Steiner
geodetic number for most distance hereditary graphs.
 BRUCE REED, School of Computer Science, McGill University
An odd version of Hadwiger's conjecture

A clique minor of order l is a set of l vertex disjoint trees
between every pair of which there is an edge. It is odd if we can two
colour it so that each tree is properly coloured but every edge between
the trees is monochromatic. About 10 years ago Gerards and Seymour
conjectured that if a graph contains no odd clique minor of order l
then it is l1 colourable. We prove an approximate version of this
result and discuss some related results. This is joint work with an
author list which has not yet been fully determined but includes
Gerards and Seymour.
 NICK WORMALD, University of Waterloo, Waterloo, Ontario N2L 3G1
Tournaments with many Hamilton cycles

The object of interest is the maximum number, h(n), of Hamilton
cycles in an ntournament. By considering the expected number of
Hamilton cycles in various classes of random tournaments, we obtain new
asymptotic lower bounds on h(n). The best result so far is
approximately 2.85584¼ times the expected number g(n) of
Hamilton cycles in a random ntournament, and it is conjectured that
h(n) ~ cg(n) where c » 2.855958. The same statements hold
for Hamilton paths.
 ROGER YU, Cariboo

 BING ZHOU, Trent University, Peterborough, Ontario K9J 7B8
List colouring the hypergraph of maximal cliques of
planar graphs

We consider some problems related to colouring and listcolouring the
hypergraph of maximal cliques of planar graphs. In particular, we show
that if each edge in a planar graph G lies on at least one 3cycle,
then the hypergraph of maximal cliques of G is 2choosable.

