




Graph Theory / Théorie des graphes (B. Aslpach, Organizer)
 P. BALISTER, University of Memphis, Memphis, Tennessee 38152, USA
Cycle decompositions

The Alspach conjecture proposes necessary and sufficient conditions for
a complete graph K_{n} (n odd) or a complete graph minus a 1factor
(n even) to be decomposable as an edgedisjoint union of cycles of
prescribed lengths. We discuss various results on this and some related
conjectures. In particular we describe some recent partial results on
the corresponding questions for complete bipartite graphs and complete
digraphs.
 E. DOBSON, Department of Mathematics and Statistics, Mississippi State
University, Mississippi State, Mississippi 39762, USA
On isomorphisms of circulant digraphs of bounded degree

C. H. Li recently made the following conjecture: Let G be a
circulant digraph of order n = n_{1}n_{2} and degree m, where gcd(n_{1},n_{2}) = 1, n_{1} divides 4k, where k is odd and squarefree,
and every prime divisor of n_{2} is greater than m, or, if G
is a circulant graph, every prime divisor of n_{2} is greater than
2m. Then if G¢ is any circulant (di)graph of order n, then
G and G¢ are isomorphic if and only if they are
isomorphic by a group automorphism of Z_{n}. We verify that
this conjecture is true.
 L. GODDYN, Simon Fraser University, Burnaby, British Columbia V5A 1S6
Circular flows and tensions on maps of high edge width

The classical dual relation between flows and colourings in plane
graphs breaks down for maps on higher surfaces. Specifically, if
S is a surface different from the sphere, then the circular
chromatic number of a map G on S may be strictly greater than
the circular flow number of the surface dual map G^{S*}. We
show that these two parameters are nearly equal provided that G has
edge width at least f(S) for some (astronomical)
function f.
Conversely, we use orientations to derive lower bounds on the circular
flow numbers of certain maps, paying special attention to a certain
exceptional class of nonorientable maps. Together, the results imply
that there are gaps in the range of possible circular chromatic numbers
for certain maps of high edge width. For example any triangulation G
has circular chromatic number either at least 4 or at most
3+e where e depends only on S and on the edge
width of G. This is joint work with M. DeVos, B. Mohar, D. Vertigan
and X. Zhu.
 P. HELL, Simon Fraser University, Burnaby, British Columbia V5A 1S6
Intersection graphs and list homomorphisms

This talk will introduce a new family of intersection graphs which
generalizes interval graphs, interval bigraphs, and circular arc graphs
of clique covering number two. A structural characterization will be
given, akin to the LekkerkerkerBoland characterization of interval
graphs. This family arose in the classification of the complexity of
list homomorphism problems, as the largest family for which polynomial
algorithms are possible (as long as P ¹ NP); this connection will
also be briefly discussed. This is joint work with Tomas Feder and
Huang Jing.
 J. JANSSEN, Dalhousie University, Halifax, Nova Scotia B3H 3J5
A listcolouring algorithm for seriesparallel graphs

Most work on list colourings has focused on determining the list
chromatic number: the minimum size of the lists so that a valid list
colouring can always be found, regardless of the content of the lists.
However, a list colouring may exist, even when the lists do not have
the size prescribed by the list chromatic number (for example, the
lists could be disjoint). This leads to the alternative question: given
a graph and a particular assignment of lists to its vertices, is it
possible to determine easily whether a list colouring exists?
We present an algorithm that answers this question for seriesparallel
graphs. Given a seriesparallel graph, the algorithm will either find a
list colouring, or establish that no such colouring exists. The
algorithm has complexity O(d^{2}m), where d is the maximum
degree and m is the number of edges of the graph.
This is joint work with Philippe Maheux.
 D. MARUSIC, University of Ljubljana, IMFM, Jadranska 19, 1000 Ljubljana,
Slovenia
Cubic semisymmetric graphs on up to 768 vertices

We discuss cubic semisymmetric, that is, regular edge but not
vertextransitive graphs. A recently obtained list of all such graphs
of order up to 768 will be presented. These graphs can be arranged in
a lattice displaying, for each member, all of its direct normal
quotients (some of which are arctransitive) and all of its direct
covers in the list. The major part of the list is comprised of graphs
with a solvable automorphism group. These graphs can be obtained as
successive regular elementary abelian covers of K_{3,3} or K_{4}. As
for the graphs with a nonsolvable automorphism group, the list includes
biquasiprimitive examples as well as graphs which have K_{1,3} as a
normal quotient. Moreover, a brief summary of all known infinite
families of cubic semisymmetric graphs together with respective members
which appear in the list, and explicit rules for their construction,
will also be given.
This is a joint work with Marston Conder, Aleksander Malnic and
Primoz Potocnik.
 M. MUZYCHUK, Netanya Academic College, Kibbutz Galuyot St. 16, Netanya 42365,
Israel
A solution of the isomorphism problem for circulant graphs

An isomorphism problem for circulant graphs (Cayley graphs over the
cyclic group) is known since 1967 when \' Ad\' am conjectured (wrongly)
that two circulants are isomorphic if and only if their generating sets
are conjugate by a group automorphism. In the talk a polynomial time
algorithm which solves the above problem will be presented. It consists
of two steps. First, a special combinatorial invariant of a graph,
called the key of a graph, is computed. The circulants with
distinct keys are not isomorphic. For circulants with a given key k
there exists a small set of permutations P_{k} with the following
property: two circulants with the same key k are isomorphic if and
only if an isomorphism between them may be found inside P_{k}.
The cardinality of P_{k} is bounded by j(n) where n is the
order of a circulant and j(n) is the Euler function.
 M. SAJNA, University of Regina, Regina, Saskatchewan S4S 0A2
Almost selfcomplementary circulant graphs

A graph is called selfcomplementary if it is isomorphic to its
own complement. A circulant graph is a Cayley graph on a cyclic group.
Froncek, Rosa, and Siran, and independently, Alspach, Morris,
and Vilfred have shown that a selfcomplementary circulant graph with
n vertices exists if and only if every prime divisor of n is
congruent to 1 modulo 4. In this talk we present an extension of
the above result to circulant graphs of even order. A graph is called
almost selfcomplementary if it is isomorphic to its complement
minus a 1factor. We give necessary and sufficient conditions for
the existence of almost selfcomplementary circulants that share a
regular cyclic subgroup of the automorphism group with their isomorphic
almost complement, and describe their structure. We also discuss recent
progress in our search for almost selfcomplementary circulants that
have no regular cyclic subgroup of the automorphism group in common
with their isomorphic almost complement.
 M. SCHULTZ, University of Nevada Las Vegas, Las Vegas, Nevada 891544020, USA
Cayley maps and emorphisms

Let G be a finite group with generating set W, where W
is closed under inverses, and let p be a cyclic permutation of
W. The Cayley map M=CM(G,W,p) is an oriented 2cell
embedding of the Cayley graph Cay(G,W) such that the rotation
of arcs emanating from each vertex is determined by p. A Cayley map
is regular if its automorphism group is as large as possible. Special
types of regular Cayley maps have already been characterized. For
example, using automorphisms (antiautomorphisms) of G,
Sirán and Skoveria provide necessary and sufficient
conditions for a Cayley map to be balanced (antibalanced) and regular.
More recently mappings of a group G called skewmorphisms have been
introduced by Jajcay and Sirán and these provide a unified
theory of regular Cayley maps. We define a Cayley map
M=CM(G,W,p) to be ebalanced if
p(x^{1})=(p^{e}(x))^{1} for every x Î W. This
concept naturally generalizes the concepts of balanced and
antibalanced. We then investigate a particular kind of skewmorphism,
which we call an emorphism. Using emorphisms we establish
necessary and sufficient conditions for a Cayley map to be ebalanced
and regular. Several related results are also presented. This is
joint work with J. Martino and M. Skoviera.
 D. WITTE, Oklahoma State University, Stillwater, Oklahoma 74078, U.S.A.
Flows that are sums of hamiltonian cycles in abelian Cayley
graphs

If X is any connected Cayley graph on any finite abelian group, we
determine precisely which flows on X can be written as a sum of
hamiltonian cycles. In particular, if the degree of X is at
least 5, and X has an even number of vertices, then it is precisely
the even flows, that is, the flows f, such that å_{a Î E(X)} f(a) is divisible by 2. On the other hand, there are
infinitely many examples of degree 4 in which not all even flows can
be written as a sum of hamiltonian cycles. Analogous results were
already known 10 years ago, from work of Brian Alspach, Stephen Locke,
and Dave Witte, for the case where X is cubic, or has an odd number
of vertices.
 X. YU, Georgia Tech, Atlanta, Georgia 30332
Long cycles in graphs

The circumference of a graph G, denoted by c(G), is the length of a
longest cycle in G. In this talk, I will present several results (and
problems) about c(G) for 4connected and 3connected graphs.
 C.Q. ZHANG, West Virginia University, USA
K_{p}minor in pconnected graphs

Let G be a (k+2)connected graph where k ³ 5. We proved that
if G contains three complete graphs of order k, say L_{1}, L_{2},
L_{3} such that L_{1} ÈL_{2} ÈL_{3} ³ 3k3, then G contains
a K_{k+2}minor. This result generalizes some early results by
Robertson, Seymour and Thomas (Combinatorica, 1993) for k=4, and
Kawarabayashi and Toft for k=5. (Joint work with Kawarabayashi, Luo,
Niu)

