64 problems

Babai–Godsil conjecture. As the order of $G$ grows, almost all finite Cayley digraphs of $G$ are DRRs.

Marušič's polycirculant conjecture. Every finite vertex-transitive graph or digraph admits a nontrivial semiregular automorphism.

Babai–Godsil–Imrich–Lovász conjecture. If $(G_n)$ is neither a family of abelian groups with exponent greater than two nor a family of generalized dicyclic groups, then almost all…

Xu's conjecture. Almost all connected Cayley graphs are normal.

Polycirculant conjecture. Every vertex-transitive (di)graph is an $m$-Cayley (di)graph for some positive integer $m$; equivalently,

Let $S$ be a surface, and let an object be naturally associated to $S$ and have sufficiently rich structure. Ivanov's metaconjecture. Every such object has the extended mapping cla…

Albertson–Collins conjecture. If $n\geq 4$, then

A graph pair $(\Gamma,\Sigma)$ is nontrivial if $\Gamma$ and $\Sigma$ are coprime connected twin-free graphs and exactly one of them is bipartite. A graph pair is stable if it has…

Five-color conjecture. Every such graph $G$ has a majority distinguishing edge $5$-coloring.

Let $G$ be the automorphism group of a vertex-transitive graph. An element of $G$ is semiregular if it is fixed-point-free and all of its cycles have the same length. Marušič's con…

Let $\mathcal{G}_m^{\pm 1}$ be the graph and $\mathcal{Q}_m^{\pm 1}$ the associated polytope for modulus $m=(1-\omega)^e$, where $e\geq 2$. The relevant automorphism groups are…

A planar map is a planar graph together with its embedding, and an automorphism is a symmetry preserving the relevant map structure. Tutte's asymmetry conjecture. Almost all planar…

A derangement is a permutation with no fixed points. A transitive permutation group is elusive if it contains no derangement of prime order, and it is 2-closed if it is equal to th…

Let $G$ be a finite connected graph on at least six vertices, and let $D'_s(G)$ denote the minimum number of edge colours needed to break every small automorphism of $G$. Kalinowsk…

Stability conjecture. For a group $G$ of order $r$, the proportion of inverse-closed subsets $S$ of $G$ such that $\operatorname{Cay}(G,S)$ is stable approaches $1$ as $r$ tends to…

Strong non-automorphism conjecture. There are minimum zero forcing sets of $Q_d$ that are non-automorphic in a particularly strong sense.

Let $G$ be a graph. A graph is opposable if it has an automorphism of order two, called an opposition, such that $f(v)\notin N[v]$ for every vertex $v\in V(G)$. The second player h…

Almost-all finite graphs conjecture. Almost all finite graphs are 2-distinguishable.

A countable group is called realizable if it is the automorphism group of a Cayley graph. Watkins's conjecture. Most countable groups are realizable, except for a large class of ab…

Let $W_u$ be a Walecki tournament with vertex labelled $*$. An automorphism of $W_u$ is an isomorphism from $W_u$ to itself, and an isomorphism between two Walecki tournaments is a…

Let $n\geq 3$, let $T$ be a set of transpositions generating $S_n$, and let $G(T)$ be the graph on $[n]$ whose edges correspond to the transpositions in $T$. Consider the Cayley gr…

Let AFP denote the Annealing with Fixed Points method for approximating graph symmetries, and consider its performance on smaller graphs. Combinatorial-complexity explanation. We c…

Let $n\geq 9$ be a composite integer. A nut graph is a graph whose adjacency matrix has nullity one and whose nullspace is spanned by a vector with no zero entries; write $o_v(G)$…

Let $G$ be a graph with edge weights, let $\lambda_2(G;\omega)$ denote its algebraic connectivity, and let $R(G;\omega)$ denote its total effective resistance. Define … A weight di…

Brooks et al.'s conjecture.