46 problems

Hamiltonian path pattern conjecture. In order for a Hamiltonian path to exist on $I[G]$, it is necessary and sufficient that $I[G]$ satisfy one of the four possible patterns:

Buratti-Horak-Rosa conjecture. If

Let $K_n$ be the complete graph on $n$ vertices, and let edge lengths be the integers from $1$ through $\lfloor n/2\rfloor$, with the length of an edge defined by the cyclic distan…

Let $Q_n$ be the graph whose vertices are the subsets of $[n]:=\{1,\ldots,n\}$, with edges joining sets that differ in a single element. A matching is a set of pairwise vertex-disj…

Let $K_v$ be the complete graph on $\{0,1,\dots,v-1\}$, and define the edge length by … Let $L$ be a list of $v-1$ positive integers not exceeding $\lfloor v/2\rfloor$. Horak and R…

Let $X$ be the Cartesian product of $k$ directed cycles of lengths $m_1,m_2,\ldots,m_k$, where $k\geq 3$ and each $m_i\geq 2$. For vertices $u$ and $v$ of $X$, let $d_X(u,v)$ denot…

Let $X$) be the Cartesian product of $k$ directed cycles of lengths $m_1,m_2,\ldots,m_k$, where $k\geq 3$ and each $m_i\geq 2$, and let $u$ and $v$ be distinct vertices of $X$. Ham…

Let $n$ and $k$ be positive integers, and let $\Pi(n;k)$ be the class of graphs of order $n$ whose longest path has order $n-k$ and such that deleting any set of $k$ vertices leave…

Let $G$ be a $d$-dimensional orthotope grid graph with $d\geq3$, and let $H$ and $K$ be two distinct Hamiltonian paths of $G$. A backbite move is the endpoint-relocation move defin…

Acyclic $(3,4)$-tournament spanning-path conjecture. If $G$ is a $(3,4)$-tournament with no closed walk, then $G$ has a spanning path.

$(3,4)$-tournament spanning-path conjecture. Every $(3,4)$-tournament has a spanning path. That is, $f(n,3,4)=n$.

Let $T$ be a strong tournament of order $n\geq 8$, let $e$ be an arc of $T$, and let $P$ be an oriented path of order $n$. El Sahili's conjecture. The tournament $T-e$ contains $P$…

Let $K_n$ be the complete graph on $n$ vertices, with its edges assigned a uniformly random ordering, equivalently with independent continuous random weights. An accessible path is…

Let $K_n$ be drawn simply in the plane, and let $a,b$ be two vertices. A path is plane if no two of its edges cross. All-pairs Hamiltonian-path conjecture. For every simple drawing…

Let $L$ be a multiset of linear lengths, where $\{1^a,(y-k)^b,y^c\}$ denotes the multiset containing $a$, $b$, and $c$ copies of $1$, $y-k$, and $y$, respectively. A multiset is li…

Let $K_v$ be the complete graph on $v$ vertices, with cyclic lengths measured modulo $v$. For a multiset $L$, write $\operatorname{supp}(L)=\{x:x\in L\}$. A multiset is cyclically…

Let $Q_n$ be the $n$-dimensional hypercube. A matching is a set of pairwise vertex-disjoint edges. Let $u,v\in Q_n$ be vertices of opposite parity, and let the C-conditions be the…

Let $Q_n$ be the $n$-dimensional hypercube. A maximal matching is a matching that cannot be enlarged by adding an edge. For a matching $M$ and a vertex $u$ covered by $M$, let…

Let $Q_n$ be the $n$-dimensional hypercube. A half-layer is the set of edges in one direction having a fixed parity, and an almost half-layer is a set of edges missing one edge fro…

Coprime Buratti–Horak–Rosa conjecture. If $L$ is a multiset of size $v-1$ such that

Let $K_n$ be the complete graph, let $\mathcal{D}$ be a simple drawing of it on $n\ge 2$ vertices, and let $v$ and $w$ be distinct vertices of $\mathcal{D}$. A crossing-free Hamilt…

Prescribed-difference partitioning conjecture. There exists a partition of $Q$ into convex polygonal regions $Q_1,\dots,Q_s$ such that, for every $i$, the segment $p_ip_{i+1}$ is a…

Traceability conjecture. For every integer $k\geq 2$, every $k$-traceable oriented graph of order at least $2k-1$ is traceable.

Aichholzer–Orthaber–Vogtenhuber's conjecture. For each pair of vertices $s,t$ in a simple drawing of $K_n$, there exists a plane Hamiltonian path from $s$ to $t$.

Let $P$ be a finite sign-balanced poset, and let $\mathcal G(P)$ be the graph whose vertices are the linear extensions of $P$ and whose edges correspond to adjacent switches. Ruske…