104 problems

Cycle-with-chords conjecture. If $G$ has average degree at least $C\log\log(n)$, then $G$ contains a cycle $C$ on $[202~\ell$ vertices with at least $[203~\ell/2$ chords, for some…

Let $C_n$ and $C_m$ be cycles with $n,m\geq 3$. A supermagic labeling of a graph with $q$ edges is a bijection from its edge set to $\{1,2,\dots,q\}$ such that the sums of the labe…

Two edge-disjoint cycles are nested with no geometric crossings when the vertex set of one is contained in that of the other and the two cycles can be drawn together in the plane w…

A decomposition of a graph is a partition of its edge set into subgraphs of the indicated types. Erdős–Gallai conjecture. Every $n$-vertex graph has a decomposition into $O(n)$ cyc…

For a graph $G$, let $N(C_q,G)$ denote the number of copies of the cycle $C_q$ in $G$, and let $\operatorname{ex}(n,C_q,\mathcal C_{\ge L+1})$ be the maximum possible value of…

Let $C_n$ and $C_m$ be cycles with $n,m\geq 3$, let $J_{C_n,C_m}$ be their associated binomial edge ideal, and let $\ell(J_{C_n,C_m})$ denote its analytic spread. Assume that the c…

For a digraph $D$, its minimum out-degree is the minimum number of outgoing edges over all vertices of $D$. Lichiardopol's conjecture. For every $k\geq1$, there exists an integer…

For a digraph $D$, a set of directed cycles has distinct lengths when no two of its cycles have the same length. Half-integral distinct-length directed-cycle conjecture. For every…

For a graph $G$, let $\Lambda(G)=\{\ell\in\mathbb{N}\mid G\text{ contains a cycle of length }\ell\}$, and let $G-X$ denote the graph obtained by deleting the vertices in $X$. Disti…

For a graph $H$, let $\chi(H)$ denote its chromatic number and $|H|$ its number of vertices. A graph $G$ is $H$-good if…

All graphs under consideration are finite and simple. For a graph $G$ and a vertex $v$, let $d_G(v)$ denote the degree of $v$. Dean's conjecture. For every integer $k \ge 3$, every…

Let $C_a^\mathrm{mon}$ be a monotone cycle of order $a$ and $P_b^\mathrm{alt}$ an alternating path of order $b$. Monotone-cycle–alternating-path conjecture. For any $a \ge 3$ and…

Let $G$ be a cycle on $n\ge 3$ vertices. Its dominion is the invariant denoted by $\zeta(G)$. Cycle dominion conjecture. If $G$ is a cycle on $n\ge 3$ vertices, then … The cases…

Let $G$ be a $k$-connected graph with $k\geq 2$, and let $F$ be a linear forest, meaning a graph whose components are paths, that is a subgraph of $G$ with $l$ edges and $t$ isolat…

Let $G$ be a graph on $n$ vertices, let $\delta(G)$ denote its minimum degree, and let a cycle of maximum order mean a cycle containing the maximum possible number of vertices in…

Odd-cycle avoidability conjecture. All orientations of odd cycles are avoidable.

Strong hub cover pebbling conjecture for cycles.

Let $G$ be a graph with the maximum possible number of edges among graphs that do not contain $k$ cycles of consecutive even lengths. A block is a maximal connected subgraph with n…

Let $G$ be an $n$-vertex graph, and let $e(G)$ denote its number of edges. Say that $G$ contains $k$ cycles of consecutive even lengths when it contains such a collection of cycles…

A graph is degree 3-critical if it has $n$ vertices, $2n-2$ edges, and no proper induced subgraph with minimum degree at least $3$. Narins–Pokrovskiy–Szabó conjecture. Every degree…

An empty $k$-cycle in a simple drawing of $K_n$ is a plane cycle through $k$ vertices such that all remaining vertices lie on one common side. Bergold et al.'s conjecture. Every si…

For an integer set $I$, let $\mathcal{C}_I$ denote the family of cycles whose lengths belong to $I$, and let $\operatorname{sat}(n,\mathcal{C}_I)$ be the minimum number of edges in…

For an integer set $I$, let $\mathcal{C}_I$ denote the family of cycles whose lengths belong to $I$, and let $\operatorname{sat}(n,\mathcal{C}_I)$ be the minimum number of edges in…

Let $\mathcal{C}_I$ denote the family of cycles whose lengths belong to an integer set $I$, and let $\operatorname{sat}(n,\mathcal{C}_I)$ be the minimum number of edges in an $n$-v…

For a positive integer set $I$, let $\mathcal{C}_I$ denote the family of cycles whose lengths belong to $I$, and let $\operatorname{sat}(n,\mathcal{C}_I)$ be the minimum number of…