59 problems

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

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

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

McKay–Praeger conjecture. As the order of the (di)graphs grows,

A vertex-transitive graph is a graph whose automorphism group acts transitively on its vertices. Thomassen's conjecture. There are only finitely many connected vertex-transitive gr…

Gruslys's conjecture. If $|V(H)|$ divides $|V(G)|$, then there exists a positive integer $n$ such that $G^n$ admits a perfect induced $H$-packing.

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…

For each integer $n\ge 3$, let $\ell(n)$ be the maximum integer such that every connected vertex-transitive graph of order $n$ contains a cycle of length at least $\ell(n)$. The st…

Hamiltonian conjecture for vertex-transitive graphs. Every connected vertex-transitive graph, with the exception of the five graphs listed below, possesses a Hamilton cycle.

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…

A finite simple graph is vertex-transitive if its automorphism group acts transitively on its vertices, and a Cayley graph is a graph constructed from a group and a generating set…

A Cayley graph is a graph associated with a group and a generating set; let $K_2$ denote the complete graph on two vertices. Folklore Hamiltonicity conjecture. Except for $K_2$, ev…

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

Let $X$ be a vertex-transitive graph. An automorphism of $X$ is semiregular if it fixes no vertex and all of its orbits on the vertices have the same length. The semiregular automo…

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…

A graph is vertex-transitive if its automorphism group acts transitively on its vertices, and a graph is a Cayley graph if it is isomorphic to a graph generated by a group and a co…

Cameron–Spiga conjecture. The value $m(n)$ tends to $\infty$ as $n$ tends to $\infty$; equivalently, for every integer $n$, there is a constant $c_n$ such that every cubic vertex-t…

A graph's circumference is the maximum number of vertices in a cycle of the graph. A graph is vertex-transitive if, for every pair of vertices $u,v$, there is an automorphism mappi…

Degree-three conjecture. The tight minimum degree guaranteeing that every pair of vertices in a vertex-transitive digraph is separable is $d=3$.

Strengthened fixed-edge bound conjecture. For valency $4$, the bound $1/3$ in the classification theorem should be strengthened to $1/4$, eventually including some more small excep…

Let $G$ be a vertex-transitive graph, let $\Delta(G)$ denote its maximum degree, and write $mbt(G)$ for its book thickness. Put $\Delta(G)=r$. Vertex-transitive book-thickness conj…

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…