---

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 1-factor (n even) to be decomposable as an edge-disjoint 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₁n₂ and degree m, where gcd(n₁,n₂) = 1, n₁ divides 4k, where k is odd and square-free, and every prime divisor of n₂ is greater than m, or, if G is a circulant graph, every prime divisor of n₂ 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 Lekkerkerker-Boland 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 list-colouring algorithm for series-parallel 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 series-parallel graphs. Given a series-parallel graph, the algorithm will either find a list colouring, or establish that no such colouring exists. The algorithm has complexity O(d²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 vertex-transitive 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 arc-transitive) 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₄. 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 self-complementary circulant graphs

A graph is called self-complementary 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 self-complementary 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 self-complementary if it is isomorphic to its complement minus a 1-factor. We give necessary and sufficient conditions for the existence of almost self-complementary 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 self-complementary 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  89154-4020, USA
Cayley maps and e-morphisms

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 2-cell 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 skew-morphisms 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 e-balanced 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 skew-morphism, which we call an e-morphism. Using e-morphisms we establish necessary and sufficient conditions for a Cayley map to be e-balanced 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 4-connected and 3-connected graphs.

C.-Q. ZHANG, West Virginia University, USA
K_p-minor in p-connected 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₁, L₂, L₃ such that |L₁ ÈL₂ ÈL₃| ³ 3k-3, 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)