191 problems

Burr–Erdős conjecture. Every $n$-vertex graph without cycles of length $\ell$ modulo $k$ has at most a linear number of edges in $n$.

Let $F$ be a fixed graph, let $v(F)$ denote its number of vertices, and let $ind(F)$ denote its inducibility. For a cycle $C_k$ with $k\geq 5$, Pippenger and Golumbic conjectured t…

Let $K_n$ be a complete graph whose edges are coloured with two colours. A monochromatic cycle is a cycle all of whose edges have the same colour. Lehel's conjecture. The vertex se…

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…

Let $G$ be a graph, and let $\Lambda(G)=\{\ell\in\mathbb{N}\mid G\text{ contains a cycle of length }\ell\}$ be its cycle spectrum. A condition on graphs is non-trivial if it does n…

Erdős–Simonovits–Sós conjecture.

Consider graphs with minimum degree at least $3$. Erdős–Gyárfás conjecture. Minimum degree $3$ should suffice to guarantee a cycle whose length is a power of $2$. The source notes…

Let $k\geq 2$ and let $n\geq 3$ be odd. Write $R_k(C_n)$ for the $k$-color Ramsey number of the cycle $C_n$, namely, the least integer $N$ such that every $k$-edge-coloring of…

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…

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_{2k}$ be an even cycle of length $2k$, and let $n$ be the number of vertices of a planar graph. Cox–Martin conjecture. The maximum number of copies of $C_{2k}$ in an $n$-ver…

For integers $r,k\geq 3$, let $C_k^r$ be the loose $k$-cycle in an $r$-uniform hypergraph: its edges $e_1,\dots,e_k$ satisfy $|e_i\cap e_{i+1}|=1$ cyclically, and every other pair…

Caro's conjecture. For every odd $q\ge5$,

Saturation spectrum conjecture.

A cycle $C_n$ is a graph with $n$ vertices and $n$ edges, and a graph is perfect edge-magic if it admits an edge-magic labeling whose induced edge sums attain every possible valenc…

Lovász–Woodall conjecture. If $k$ is even or $G-S$ is connected, then $G$ contains a cycle containing every edge in $S$.

Let $G$ be a $2$-connected graph with minimum degree at least $3$, and let a longest cycle mean a cycle of maximum length in $G$. Harvey's conjecture. Every longest cycle of $G$ ha…

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…

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$. Erdős–Faudree–Gyárfás–Schelp conjecture. Every d…

Let $G$ be an $n$-vertex graph whose edges are coloured with two colours, and suppose that … A monochromatic cycle is a cycle all of whose edges have the same colour. Balogh–Barát–…

For an integer $r\geq 5$, let $C_r$ denote the cycle on $r$ vertices, and let $rsat(n,C_r)$ be its rainbow saturation number. Asymptotic rainbow saturation conjecture for cycles. T…

Let $\operatorname{\mathsf{C}}_{n}$ denote the cycle graph on $n$ vertices. A graph is $\mathcal{L}$-DS when its normalized Laplacian spectrum determines it up to isomorphism. Butl…

Let $d(G)$ denote the average degree of a graph. A pillar consists of two vertex-disjoint cycles of the same length, … and vertex-disjoint paths $P_1,\ldots,P_\ell$ of the same len…

Kovács–Soltész conjecture. The equality

For an integer $ell\geq 3$, let $\mathscr{F}_{\ell}$ be the family of cycles of length at least $ell$ in a graph $G$. A set $X\subseteq V(G)$ is a transversal of…