141 problems

Hamiltonicity conjecture. The graph $G(L(P))$ has a Hamiltonian cycle.

Conjecture on fixed-vertex extensions. For every fixed integer $k$, there exists a polynomial-time algorithm for deciding whether such a digraph has a Hamiltonian cycle.

Let ${\cal H}$ be the set of Hamiltonian cycles in $K_n$. For a family of winning sets ${\cal F}$, let $b_{\cal F}^p$ denote the smallest bias for which Breaker wins the random gam…

Let $P$ be an even simple $3$-polytope, meaning that every facet of $P$ has an even number of vertices. Its vertex-edge graph is the graph whose vertices and edges are those of $P$…

Let $H$ be a red/blue coloured $3$-graph on $n$ vertices, and let $\delta_1(H)$ denote its minimum vertex degree. A loose Hamilton cycle is a cyclic ordering of the vertices in whi…

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…

DeBiasio's conjecture. Every $n$-vertex digraph $D$ satisfying

Let $G$ be a simple graph with $n$ vertices and minimum degree $\delta(G)\geq 3$, and suppose that $G$ contains a Hamiltonian cycle. Girao, Kittipassorn, and Narayanan's conjecture…

For a fixed integer $r\ge 2$, let $K_r$ denote the complete graph on $r$ vertices, and let $\alpha^*(K_r)$ be the minimum-degree threshold of Hamiltonicity for perturbation by a un…

Let $n\in\mathbb{N}$ with $n\geq 3$, and let $\mathcal{G}=\{G_i:i\in[n]\}$ be a family of $n$-vertex graphs with the same vertex set; the graphs in the family may be identical. For…

Let $D$ be a digraph on $n\geq 3$ vertices, with nondecreasing out-degree sequence $d_1^+\leq\cdots\leq d_n^+$ and in-degree sequence $d_1^-\leq\cdots\leq d_n^-$. Nash-Williams' di…

Let $D$ be a strongly connected digraph on $n$ vertices, with nondecreasing out-degree sequence $d_1^+\leq\cdots\leq d_n^+$ and in-degree sequence $d_1^-\leq\cdots\leq d_n^-$. Nash…

Let $W:\Omega^2\to[0,1]$ be a graphon, let $k\ge 2$ be fixed, and let $\mathbb{G}(n,W)$ be the associated inhomogeneous random graph. A $K_{k+1}$-fractional cover of $W$ is a measu…

Let $W:\Omega^2\to[0,1]$ be a graphon, and let $\mathbb{G}(n,W)$ denote the associated inhomogeneous random graph. The four conditions in Proposition are: $W$ is not a connected gr…

Han–Zhao's conjecture. If

Let $G$ be a strongly edge-colored graph on $n$ vertices, and let $\delta(G)$ denote its minimum degree. Cheng, Sun, Tan and Wang's conjecture. If … then $G$ has a rainbow Hamilton…

For integers $k\geq2$ and $m$, let $\bar\eta_{k,m}$ denote the $(k,m)$-Dirac over-exponent, and let $f(\ell_{k,m})$ be the quantity defined in the paper. The asymptotic over-thresh…

Let $G$ be an $(n+1)$-regular graph on $2n$ vertices. A subset $S\subseteq V(G)$ is called Hamiltonian when the induced subgraph $G[S]$ contains a Hamilton cycle. Erdős–Faudree con…

Let $n\geq 2$ be an even integer. A perfect $1$-factorisation of a graph is a partition of its edge set into perfect matchings such that the union of any two distinct perfect match…

For an even integer $n$, let $f(n)$ be the maximum integer $k$ such that some $k$-regular graph $G$ on $n$ vertices admits a flawless 1-factorization, meaning a perfect 1-factoriza…

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…

Hung's conjecture. An $n$-dimensional augmented cube admits a Hamiltonian decomposition.

Häggkvist's conjecture. If

Let $G$ be a strongly connected digraph on $n\geq 3$ vertices, and let $d^+_1\leq\cdots\leq d^+_n$ and $d^-_1\leq\cdots\leq d^-_n$ be its ordered outdegree and indegree sequences.…

Let $G$ be an $n$-vertex $d$-regular graph, and let $F \sim G_{n,2}$ be a uniformly random 2-factor, that is, a spanning 2-regular graph, on the same vertex set. Draganić–Keevash c…