27 problems

Let $G_n$ be a family of vertex-transitive bipartite graphs with $|G_n|\to\infty$. Let $\Delta_n$ denote the diameter of $G_n$, and let $f_n$ be uniformly random in…

Let $G$ be a finite, connected, vertex-transitive graph. Write $\operatorname{diam}(G)$ for its diameter and, for a vertex set $S$, let $\partial S$ denote its edge boundary. Isope…

Lovász's conjecture. Every connected vertex-transitive graph has a Hamilton path.

Dewar's conjecture. There exists a function $f \colon \mathbb{N}\rightarrow \mathbb{N}$ with the following property. For $d\in \mathbb{N}$, if $G$ is a vertex-transitive graph of d…

Let $G$ be a finite connected vertex-transitive graph. A graph is Hamilton connected if it has a Hamilton path between any two vertices, and Hamilton laceable if it is bipartite an…

Critical bias ratio conjecture. If $\Lambda$ is a connected vertex-transitive graph, then

Coarse Thomassen theorem. Either $G$ is quasi-isometric to a planar graph, or $G$ contains every finite graph as an asymptotic minor.

Let $G$ be a graph, and let $W(G)$ denote its Wiener index. A Šoltés graph is a graph for which deleting any vertex leaves the Wiener index unchanged. A graph is vertex transitive…

Let $G$ be a vertex-transitive partial cube with girth $6$. Marc's conjecture. Doubled Odd graphs are the only vertex-transitive partial cubes with girth $6$. This conjecture propo…

Let $\Gamma$ be a cubic vertex-transitive graph of order $n$ that is not isomorphic to $K_{3,3}$ or a split Praeger–Xu graph, and let $g\in\operatorname{Aut}(\Gamma)$. A regular or…

Let $\Gha$ be a vertex transitive graph with a partite presentation $P$ such that $\Gha=\operatorname{PCay}(P)$, and let $\Gpa\leq\operatorname{Aut}_{c\text{-}loc}(\Gha)$ be a tran…

Let $\Gha$ be a finite cubic vertex transitive graph, and let $M$ be a perfect matching in $\Gha$. Write $\Gha \backslash M$ for the graph obtained by deleting the edges of $M$. Lo…

Evasiveness conjecture for graphs. If $X\in D_{\infty}$ and $X$ is vertex-transitive, then $X$ is a complete graph.

A graph is vertex transitive if, for every pair of vertices $v,w$, there is a graph automorphism mapping $v$ to $w$. A graph is Hamiltonian if it admits a Hamiltonian circuit, name…

For a finite graph $G$, let $G^n$ be the graph with vertex set $V(G)^n$, in which two vertices are adjacent exactly when they differ in one coordinate and the entries in that coord…

Let $G$ be a vertex-transitive graph with stationary distribution $\pi$. For $k\;\geqslant\;2$, let $\mathrm{SC}(G,k)$ be the social connectivity time when $k$ walkers independentl…

Middle-level graph conjecture. The graph $G$ is a middle-level graph.

Let $G$ be a vertex-transitive graph with maximum degree $\Delta$, and let $s\chi(G)$ denote its strong chromatic number, the smallest $r$ such that every partition of $V(G)$ into…

Let $G$ be a vertex-transitive graph, with chromatic number $\chi(G)$, clique number $\omega(G)$, and maximum degree $\Delta(G)$. Cranston–Rabern's conjecture. Every vertex-transit…

Cameron–Sheehan–Spiga conjecture. There exists a function $f:\mathbb{N}\to\mathbb{N}$ with

For fixed $d\geq 3$, let $VT_d(n)$ be the number of isomorphism classes of $d$-valent vertex-transitive graphs of order at most $n$, and let $CAY_d(n)$ count the corresponding Cayl…

Let $d\text{-valent}$ vertex-transitive graphs, Cayley graphs, and graphical regular representations (GRRs) be counted up to order at most $n$ by $VT_d(n)$, $CAY_d(n)$, and…

Scaling-limit conjecture. Then $(X_n,d/\Delta_n)$ has a subsequence converging for the pointed GH-topology to a connected nilpotent Lie group equipped with a Carnot–Carathéodory me…

DeVos–Mohar conjecture. There exists a fixed constant $c>0$ such that

Let $G$ be a connected vertex-transitive graph, let $A\subseteq V(G)$ be finite with $0<|A|\leq \tfrac12|V(G)|$, let $\partial A$ denote the vertex boundary of $A$, and let…