17 problems

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…

Let $G$ be a graph, and let $G_p$ be obtained by retaining each edge independently with probability $p$. Suppose that $G$ satisfies the assumptions of the cited path theorem: for s…

Let $G$ be a host graph, and let $G_p$ be the random subgraph obtained by retaining each edge independently with probability $p$. The preceding result establishes long cycles under…

For a graph $G$, an induced packing of cycles is a collection of cycles with no edge between distinct cycles. For a vertex set $X$, let $B_G(X,1)$ be its closed distance-one neighb…

Let $G$ be a connected bipartite graph with bipartition $(X,Y)$. Suppose … let $h=\left\lfloor\frac{n-k}{2}\right\rfloor$, and assume that $\delta(G)\ge r\ge 1$, where $n\ge 2k+2r$…

Let $G$ be a balanced bipartite graph of order $2n$, with minimum degree $delta(G)\ge r\ge 1$, where $n\ge 2k+2r$ and $k\in\mathbb{Z}$. Adamus–Adamus conjecture. If … then $G$ cont…

Long-cycle extension conjecture. For a suitable choice of $c_3$ and $C_3$, the same conclusion holds for all $L\in[c_3^{-1},n]$.

Long's conjecture. The graph $G$ contains a path of length at least

Long's conjecture. The graph $G$ contains a path of length at least

Let $G(n,c/n)$ be the random graph on $[n]$ in which each edge appears independently with probability $c/n$, where $c>1$, and let $L_{c,n}$ denote the size of its longest cycle. Er…

Let $C$ be the minimum quantity such that every $n$-vertex Hamiltonian graph with minimum degree at least $3$ contains a second cycle of length at least $n-C$. Girã o–Kittipassorn–…

Let $G$ be a finite loopless directed graph, allowing both orientations of an edge, and write $d^+(v)$ and $d^-(v)$ for the outdegree and indegree of a vertex $v$. The graph is Eul…

Let $G$ be an $n$-vertex graph, and write $\delta(G)$ for its minimum degree. A Hamiltonian cycle is a cycle spanning all vertices of $G$. The bounded-defect cycle conjecture. If…

Let $G$ be a graph, let $p$ denote its order, let $c$ denote the length of a longest cycle, let $\kappa$ denote the connectivity of $G$, and let $\sigma_r$ denote the minimum degre…

Let $G$ be a graph, let $p$ denote its order, let $c$ denote the length of a longest cycle, and let $\sigma_r$ denote the minimum degree sum of an independent set of $r$ vertices.…

Let $G$ be a graph, let $p$ denote its order, let $c$ denote the length of a longest cycle, let $\bar\kappa(G)$ denote its connectivity, and let $\sigma_r$ denote the minimum degre…

Let $\ell\in\mathbb{N}$ be fixed, and call a cycle long if its length is at least $\ell$ and short otherwise. The lemma preceding this conjecture gives a vertex set of size governe…