 |
|
||||
Chair: Brett Stevens (Carleton University)
Org: Tara Petrie (Simon Fraser University)
[PDF]
- 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)\}$?
