279 problems

Let $G$ be a graph, let $X\subseteq V(G)$, and let $c(G-X)$ denote the number of connected components of $G-X$. Define the toughness of $G$ by … with $\tau(G)=\infty$ when $G$ is c…

Let $G$) be a simple connected graph with a Hamiltonian cycle $C$. A graph is $k$-regular if every vertex has degree $k$, and a cycle is distinct from $C$ if it is not $C$. Sheehan…

Häggkvist's conjecture. If

Let $G$ be an $(n,d,lambda)$-graph, meaning a $d$-regular graph on $n$ vertices whose non-trivial adjacency-matrix eigenvalues have absolute value at most $lambda$. Krivelevich–Sud…

Pósa-type conjecture for triple systems. For every $\varepsilon>0$, there is $n_0$ such that every $3$-uniform hypergraph $G$ of order $n\geq n_0$ satisfying

Let $G(n,p)$ be the binomial random graph on $n$ vertices, where $0\leq p=p(n)\leq 1$, and let $\delta(G)$ denote its minimum degree. Frieze–Krivelevich conjecture. With high proba…

Hamilton-cycle reconstruction conjecture. There are constants $0\leq c<1$ and $n_0\geq 0$ such that, for all integers $n\geq n_0$, the number of Hamilton cycles of an $n$-vertex gr…

Let $G$ be an $n$-vertex 4-connected planar triangulation, meaning a planar triangulation that remains connected after the removal of fewer than four vertices. A Hamiltonian cycle…

Let $r$ and $n$ be integers with $r\geq 5$ and $n\geq r+3$, and let $G$ be a Hamiltonian $r$-regular graph on $n$ vertices. Haythorpe's conjecture. The graph $G$ has at least … Ham…

Let $K_n$ be the complete graph on $n$ vertices, and let $\chi'(K_n)$ denote its edge-chromatic number. A properly edge-coloured graph is one in which adjacent edges receive distin…

A Hamilton cover of a graph $G$ is a collection of Hamilton cycles whose union contains all edges of $G$. Its size is at least $\left\lceil \frac{\Delta(G)}{2}\right\rceil$, where…

Let $G$ be an $n$-vertex Dirac graph, meaning that $\delta(G) \geq n/2$. Suppose every Dirac graph contains at least $c^n n!$ Hamilton cycles for some small positive constant $c$.…

Let $Q_n$ be the $n$-dimensional hypercube, with $n\geq 2$, and let a perfect matching be a matching that covers every vertex of $Q_n$ exactly once. Kreweras's conjecture. Any perf…

A graph is Hamiltonian if it contains a Hamiltonian cycle, and a graph is 3-regular if every vertex has degree 3. Cantoni's conjecture. Every planar 3-regular graph with exactly th…

Let $G$ be a planar graph. A graph is $K_1$-hamiltonian if deleting any one vertex produces a hamiltonian graph. Grünbaum's conjecture. Every planar $K_1$-hamiltonian graph is hami…

Let $G$ be a group with generating set $S$, and let the Cayley graph $\Gamma$ have vertex set $V(\Gamma)=G$ and edge set … A graph is Hamiltonian if it contains a cycle passing thr…

Let $K_n$ be the complete graph on $n$ vertices, with an edge-coloring that is $k$-bounded when no color appears on more than $k$ edges. A rainbow Hamiltonian cycle is a Hamiltonia…

For $varepsilon>0$, let an $(\varepsilon,d)$-expander be the sublinear-expansion notion used in the source. Hamiltonicity conjecture for regular sublinear expanders. There exists…

Han–Zhao's conjecture. If

Häggkvist–Thomason conjecture. If

Let $G$ be a finite group and let $S$ be a generating set for $G$. The Cayley graph of $G$ with respect to $S$ is the graph whose vertices are the elements of $G$, with an edge joi…

Local-resilience conjecture. There exists a sufficiently large constant $C>0$ such that, whenever $G$ satisfies this local resilience condition and every Hamilton cycle in $G$ has…

The $n$-dimensional hypercube $Q_n$ has as vertices all subsets of $[n]:=\{1,\ldots,n\}$, with edges joining sets that differ in a single element. A matching is a set of pairwise v…

Bollobás–Cooper–Fenner–Frieze conjecture. W.h.p., for every $t\geq\tau_k$, the graph $G_t^{(k)}$ spans $\left\lfloor\frac{k-1}{2}\right\rfloor$ edge-disjoint Hamilton cycles and, w…

Let $G$ be a 4-connected toroidal graph, meaning a $4$-connected graph embedded on the torus. The Grünbaum–Nash-Williams conjecture. $G$ is hamiltonian. The conjecture extends the…