62 problems

Nash-Williams' conjecture. If

Häggkvist's conjecture. If

For an $r$-edge-coloured graph $G$, let $cp(G)$ be the smallest number of vertex-disjoint monochromatic cycles partitioning $V(G)$, and define … where $\mathcal{G}(n,r,\delta)$ is…

Let $G$ be an $n$-vertex $r$-edge-coloured graph, and let $tc(G)$ be the smallest number of not necessarily vertex-disjoint monochromatic trees whose vertices cover $V(G)$. Bal–DeB…

Let $G$ be a graph with vertex set $V(G)$, and let $G$ have a $2$-edge-colouring. A partition into two cycles means two vertex-disjoint cycles whose vertices cover $V(G)$. Schelp's…

El-Zahar's conjecture. If

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…

Favaron–Shi conjecture. Every minimal $k$-factor-critical graph satisfies

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 $H$ be an $n$-vertex $k$-uniform hypergraph, and let $\delta_{k-1}(H)$ denote its minimum codegree. A tight Hamilton cycle is a Hamilton $\ell$-cycle with $\ell=k-1$, equivalen…

For $r\geq2$ and $\delta\in(0,1/2)$, let … where $\mathcal{G}(n,r,\delta)$ consists of the $n$-vertex $r$-edge-coloured graphs with $\delta(G)\geq(1-\delta)n$, and $cp(G)$ is the s…

Häggkvist–Thomason conjecture. If

Frieze–Krivelevich–Michaeli conjecture. Any strategy that uses $\varepsilon n$ fewer edges than the greedy strategy, for any constant $\varepsilon>0$, fails with high probability.

Let $G$ be an $n$-vertex graph whose edges are coloured with two colours. Balogh–Barát–Gerbner–Gyárfás–Sárközy conjecture. If the minimum degree of $G$ is greater than $3n/4$, then…

A sequence of cycles $C_1,\dots,C_k$ is admissible if $|E(C_1)|\ge 2$ and either $|E(C_{i+1})|-|E(C_i)|=1$ for every $1\le i\le k-1$, or $|E(C_{i+1})|-|E(C_i)|=2$ for every…

For a fixed integer $k \geq 4$, let a $TT_k$-factor be a collection of vertex-disjoint copies of the transitive tournament $TT_k$ covering all vertices, and let an almost $TT_k$-fa…

Let $k,\ell\in\mathbb{N}$ with $1\leq \ell<k$, and define $c_{k,\ell}^{*}$ to be the smallest number $c$ such that every $k$-uniform hypergraph $H$ on $n$ vertices with … contains…

Li, Zhou, Fujita, and Mao's conjecture. Under the optimal minimum-degree assumption, the lower bound

For integers $n$ and $c$, let $f(n,c)$ be the least integer $d$ such that every $n$-vertex graph with minimum degree at least $d$ contains a cycle with at least $c$ chords. Kára an…

All graphs are finite and simple. For a graph $G$, let \mathcal L_o(G)=\{2\ell+1:\text{G$contains a cycle of length$2ell+1}\}, let $\delta(G)$ denote its minimum degree, and…

A graph is finite and simple, and the minimum degree of a graph is the least degree among its vertices. Kára and Král's conjecture. Every graph on $31$ vertices with minimum degree…

Folklore clique decomposition conjecture.

Let $W_{2k}$ be the wheel on $2k+1$ vertices, let $G$ be a graph on $n$ vertices, and let $\delta(G)$ denote its minimum degree. Minimum-degree wheel conjecture. For all integers…

For $r\geq2$ and $\delta\in(0,1)$, let … where $\mathcal{G}(n,r,\delta)$ consists of the $n$-vertex $r$-edge-coloured graphs with $\delta(G)\geq(1-\delta)n$, and $tc(G)$ is the sma…

Let $G$ be a $k$-graph on $n$ vertices. Write $\delta_1(G)$ for its minimum vertex degree, the minimum number of edges containing any one vertex. Spanning-component conjecture. If…