CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Open Problems
Président: Brett Stevens (Carleton University)
Org: Tara Petrie (Simon Fraser University)

BRIAN ALSPACH, University of Newcastle
Orthogonalizeable Groups  [PDF]

At the first CANADAM conference in 2007 I mentioned the following problem: Given a circulant digraph with connection set $S=\{s_1,\ldots,s_t\}$, is there a directed path of length $t$ with one arc of each length from $S$? We now extend extend the problem to all finite groups. A group $G$ is {\it orthogonalizeable} if every Cayley digraph on $G$ admits either an orthogonal directed path or an orthogonal directed cycle. This relates to Gordon's definition of sequenceable groups and we introduce the notion of a {\it sequenceable} poset for attacking the following general problem: Determine which groups are orthogonalizeable.

PETER DUKES, University of Victoria
Avoiding long bicoloured cycles  [PDF]

This is an old problem of Roland Häggkvist which I believe deserves some promotion.

Over all $n$-edge-colourings of $K_{n,n}$, determine the minimum longest two-coloured cycle. Let's call this $f(n)$. I know that $f(n) \le 182$ for all $n$ and I wonder whether, for $n$ mildly large, it is the case that $$f(n)=\begin{cases} 4 & \text{if } n \text{ is a power of 2};\\ 6 &\text{otherwise}. \end{cases}$$

KEVIN HALASZ, Simon Fraser University
Olson's Conjecture  [PDF]

In 1961, Erdős, Ginzberg, and Ziv proved that, for every sequence $g_1, \ldots, g_{2n-1}$ of elements of a finite solvable group $G$ of order $n$, there exist indices $i_1,\ldots, i_n$ such that (writing the operation additively) $g_{i_1} + \cdots + g_{i_n} = 0$. In 1976, Olson eliminated the solvability condition, thereby extending the result to \emph{all} finite groups, before conjecturing:

For any sequence of $g_1, \ldots, g_{2n-1}$ of elements of a finite group $G$, then there exist indices $i_1 < \cdots < i_n$ such that $g_{i_1} + \cdots + g_{i_n} = 0$.

Save some special cases, this problem remains open.

CHUNHUI LAI, Minnan Normal University
On Haj\'{o}s conjecture  [PDF]

Haj\'{o}s conjectured that every simple even graph on $n$ vertices can be decomposed into at most $n/2$ cycles (see L. Lovasz, On covering of graphs, in: P. Erdos, G.O.H. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231 - 236 ). The survey article on this problem can be found in Chunhui Lai, Mingjing Liu[Some open problems on cycles, Journal of Combinatorial Mathematics and Combinatorial Computing 91 (2014), 51-64.] We do not think Haj\'{o}s conjecture is true.

STANISLAW RADZISZOWSKI AND XIAODONG XU, Rochester Institute of Technology, NY and Academy of Sciences, Nanning, China
A question about growth of Ramsey numbers $R(3,k)$  [PDF]

For a graph $G$, the Ramsey number $R(3,G)$ is the smallest positive integer $n$ such that every triangle-free graph of order $n$ contains $G$ in its complement. Here we focus on $G$ being $K_k$ or $K_k-e$. The asymptotics of $R(3,k)=R(3,K_k)$ was extensively studied and now it is quite well understood. It is known that $$(1/4+o(1)){k^2 / {\log k}} \leq R(3,k) \leq (1+o(1)){k^2 / {\log k}}.$$

However, the difference $R(3,G)-R(3,H)$ for concrete "consecutive" $H$ and $G$ is still very difficult to estimate, starting already with rather small cases. In general, for $K_k$ and $K_k-e$, all we know is the following:

(1) $3 \le R(3,K_k)-R(3,K_{k-1}) \le k$, easy old bounds,

(2) $R(3,K_{k-1}) \le R(3,K_k-e) \le R(3,K_k)$, trivial bounds,

(3) $4 \le R(3,K_{k+1})-R(3,K_k-e)$ (Zhu-Xu-R 2015).

Many people tried to improve on some part of (1) or (2), to no avail. A relatively simple recent construction proving inequality (3) is an interesting step towards better understanding of both (1) and (2).

Problem: Improve over any of the inequalities in (1), (2) or (3), or their combination as (3) combines parts of (1) and (2).

ROBERT ŠÁMAL, Charles University in Prague
p-free flows  [PDF]

Let $G$ be a digraph, $M$ an abelian group, $\varphi: E(G) \to M$ a flow. We say $\varphi$ is $p$-free if $\varphi(e_1) + \dots + \varphi(e_k)$ is never zero for $1 \le k \le p$ and $e_1, \dots, e_k \in E(G)$.

For $p=1$ this is the nowhere-zero flow.

For $p=2$ this is called antisymmetric flow.

\textbf{Conjecture} (Nešetřil, Šámal) For every $p \ge 1$ exists a $K_p$ such that any orientation of an $(p+1)$-edge-connected graph has a $p$-free flow $\varphi: E(G) \to M$ where $M$ is a group of order $\le K_p$.

True for $p=1, 2$. (Jaeger; DeVos, Johnson and Seymour)

True for any $p$ and $(2p+1)$-edge-connected graphs.

Open for other cases.

JERRY SPINRAD, Vanderbilt University
Local Improvement for Coloring  [PDF]

This is a problem which came up in a class, and I could not determine the answer. Given a coloring of a graph, is there a pair of colors i, j such that we can recolor only vertices with these 2 colors, while using only 1 new color k.

Note that this seems very similar to list coloring of bipartite graphs, which is NP-complete; however, in this problem there is the extra condition that all vertices may be colored k.

XIA ZHANG, University of Victoria, Canada; Shandong Normal University, China
The correlation between f-chromatic class and gc-chromatic class of a simple graph  [PDF]

An $f$-$coloring$, a $g_c$-$coloring$ of graph $G$ is an edge-coloring such that the edge-induced subgraph of each color is a $(0,f)$-factor, $(g,d)$-factor, respectively.

Theorem 1. (S.L. Hakimi and O. Kariv, 1986) A simple graph $G$ has either $\chi_f'(G)=\Delta_{f}(G)$ ($f$-class 1), or $\chi_f'(G)=\Delta_{f}(G)+1$ ($f$-class 2), where $\Delta_{f}(G)= \max\limits^{}_{v\in V(G)}\{\lceil\frac{d(v)}{f(v)}\rceil\}.$

Theorem 2. (H. Song and G. Liu, 2005) A simple graph $G$ has either $\chi_{gc}'(G)=\delta_{g}(G)$ ($g_c$-class 1), or $\chi_{gc}'(G)=\delta_{g}(G)-1$ ($g_c$-class 2), where $\delta_{g}(G)= \min\limits^{}_{v\in V(G)}\{\lfloor\frac{d(v)}{g(v)}\rfloor\}.$

Problem. (G. Liu and X. Zhang) What kinds of simple graphs $G$ have coincident classification results between $f$-coloring and $g_c$-coloring when $\{v: d(v)=\Delta_f(G)f(v)\}=\{v: d(v)=\delta_g(G)g(v)\}$?


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan