98 problems

For every sufficiently large integer $d$ and every sufficiently large $n$, every $n$-vertex $d$-regular sublinear expander contains a Hamiltonian cycle.

Sheehan's conjecture. There is no finite $r$-regular graph with a unique Hamilton cycle for any $r>2$.

Let $G$ be a hamiltonian loopless graph with $n$ vertices, and let $P(G,t)$ denote its chromatic polynomial. Thomassen's conjecture. … The conjecture extends the known zero-free in…

Bedert–Drăganić–Müyesser–Pavez-Signé conjecture. There is an absolute constant $C$ such that, for every connected Cayley graph $G$ of order $n$ and degree $d$, the condition

Rapaport–Strasser conjecture. Every connected Cayley graph on a finite group with at least three elements has a Hamilton cycle.

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

Seymour's conjecture. For positive integers $n$ and $k$ with $n\geq k+1$ and $k\geq2$, if

Kao's conjecture. If $n\geq 4\Delta(G)-2$ and $G\Box P_n$ is balanced bipartite, then $G\Box P_n$ is hamiltonian.

Berikkyzy–Hogenson–Kirsch–McDonald conjecture. If $t\leq \left\lfloor\frac{n+\ell}{2}\right\rfloor$, then, for sufficiently large $n$,

Hilton's conjecture. For every integer $\ell$ with $3\le \ell\le n$,

Let $C_n^k$ denote the $k$th power of the cycle on $n$ vertices, and let $\varepsilon>0$. The random sub-sampling local-resilience conjecture. There exists $k$ large enough such th…

For integers $d\geq 1$, let $T_d(n,r)$ be the random graph obtained by sampling $n$ random points of the $d$-dimensional torus $(\mathds{R}/\mathds{Z})^d$ and joining two vertices…

Let $n$ and $k$ be positive integers. Consider the Cayley graph on $4\mathds{Z}/n\mathds{Z}4$ with generating set $\{-k,\ldots,k\}\setminus\{0\}$. Espuny Díaz, Lichev, and Wesolek'…

Conjecture. There exists a constant $n_s$ depending on $s$ such that $G$ is not uniquely Hamiltonian whenever $n\geq n_s$.

Dai–Zhang–Broerama–Zhang conjecture. Every $(r-1)$-connected $K_{1,r}$-free split graph is Hamiltonian.

Root-separation conjecture. For any $\alpha\the 2$, $g_0(n,\alpha)=0$ has exactly one real root for $x\the(3,+\infty)$. For any $\alpha>2$, $g_1(n,\alpha)=0$ has at most one real r…

Ryjáček et al.'s conjecture. Every $4$-connected line graph with minimum degree at least $5$ is Hamiltonian.

Ryjáček et al.'s conjecture. Every $4$-connected ${K_{1,4},K_{1,4}+e}$-free graph with minimum degree at least $6$ is Hamiltonian.

Let $G$ be a Cayley graph on $n$ vertices with degree $d$, and let $G_p$ be the random graph obtained by retaining each edge of $G$ independently with probability $p$. Random Cayle…

Given a finite group $G$ and a symmetric subset $S\subset G$, the Cayley graph $\operatorname{Cay}_G(S)$ has vertex set $G$ and edges $\{g,gs\}$ for $g\in G$ and $s\in S$. A graph…

Let $c$ satisfy $1/2<c\leqslant1$, let $G$ be an $n$-vertex graph with minimum degree $\delta(G)\geqslant cn$, and suppose the edges of $G$ are properly edge-coloured. Colourful Ha…

Hamiltonicity conjecture. Every connected bicirculant, except for the complete graph $K_2$ and the generalized Petersen graphs $G(m,2)$ with

Let $G$ be a graph. It is claw-free if it has no induced subgraph isomorphic to a claw, and $G$ is 4-connected if deleting fewer than four vertices does not disconnect it. Matthews…

Let $G$) be a 3-connected non-Hamiltonian graph. Let $K_{3,4}$ be the complete bipartite graph, let $\mathfrak{Q}^+$ be obtained from the cube by adding a new vertex adjacent to th…

Faudree–Schelp conjecture. Every such pair $u,v$ has a path of every length $k$ in this range. The conjecture was disproved by Thomassen, who constructed hamiltonian-connected grap…