171 problems

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

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

Barnette's conjecture. Every planar, $3$-connected, cubic bipartite graph is Hamiltonian.

Bollobás–Erdős conjecture. If

Hamiltonicity conjecture. The following four statements are equivalent, and each holds:

Tait's conjecture. Every $3$-regular, $3$-connected, planar graph is Hamiltonian.

Let $G$ be a graph on $n\geq 3$ vertices, let $r$ be a positive integer, and let $\delta(G)$ denote the minimum degree of $G$. The $r$-th power $\mathcal{C}^r$ of a Hamilton cycle…

Let $G$ be a graph, and let $\Lambda(G)=\{\ell\in\mathbb{N}\mid G\text{ contains a cycle of length }\ell\}$ be its cycle spectrum. A condition on graphs is non-trivial if it does n…

Komlós's conjecture. Every graph $G$ with minimum degree $d$ satisfies

Let $K_n$ be the complete graph on $n$ vertices, with $n\geqslant5$, and suppose its edges are properly edge-coloured. A Hamilton path is a spanning path, and it is rainbow when al…

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…

Hamiltonian conjecture for Cayley graphs. Every connected Cayley graph on a finite group is Hamiltonian.

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

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…

Let $G$ be a $t$-connected regular graph on $n$ vertices, with degree at least $n/(t+1)$. Bollobás–Häggkvist conjecture. The graph $G$ is Hamiltonian. This conjecture is known for…

Let $G$ be a connected, infinite, locally finite $L_1$-graph on at least three vertices. Write $N(u)$ for the neighborhood of a vertex $u$, $d(u,v)$ for the graph distance, and let…

Shi and Shan's conjecture. If $G$ is a 1-tough, $2k$-connected, $(K_2\cup kK_1)$-free graph, then $G$ is Hamiltonian.

Diestel's conjecture. The Freudenthal compactification of $G$ contains a circle through all vertices and ends of $G$.

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…

Let $G$ be a graph on $n\ge3$ vertices, with Laplacian eigenvalues $\lambda_2(G)$ and $\lambda_n(G)$. Gu's conjecture. There exists an absolute constant $c<1$ such that, if … then…

Häggkvist's conjecture. If $G$ is a Dirac graph and $\mathcal{F}$ is a 1-bounded incompatibility system for $G$, then $G$ contains an $\mathcal{F}$-compatible Hamilton cycle.

Matthews–Sumner conjecture. Every $4$-connected claw-free graph is hamiltonian.

Hendry's conjecture. Every Hamiltonian chordal graph is fully cycle extendible.

Let $G$ be a finite non-trivial connected Cayley graph. A Hamilton cycle is a cycle containing every vertex of $G$. Cayley graph Hamilton cycle conjecture. Every finite non-trivial…

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