44 problems

Odd-colour phase-transition conjecture. One has

The conjecture. The maximum order of a $k$-connected subgraph using at most two colours in every $6$-colouring of $K_n$ satisfies

Let $H$ be a red/blue coloured $3$-graph on $n$ vertices, and let $\delta_1(H)$ denote its minimum vertex degree. A loose Hamilton cycle is a cyclic ordering of the vertices in whi…

Constant-deviation conjecture. There exists an absolute constant $C$ such that for all positive integers $k$ and $t$, every colour-balanced $k$-edge-colouring of $K_{2kt}$ admits a…

Pardey and Rautenbach's conjecture. For all integers $k\geq 2$ and $t\geq 1$, every colour-balanced $k$-edge-coloured $K_{2kt}$ admits a perfect matching $M$ satisfying…

Let $c$ satisfy $1/2<c\leqslant1$, and let $G$ be an $n$-vertex graph with minimum degree $\delta(G)\geqslant cn$. Colourful tree embedding conjecture. There exists a constant…

Let $c$ satisfy $1/2<c\leqslant1$, let $G$ be an $n$-vertex graph with minimum degree $\delta(G)\geqslant cn$, and suppose the edges of $G$ are properly edge-coloured. Colourful Ha…

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…

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…

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 $k\ge2$ be an integer, let $K$ be a finite clique, and let $c$ be a $k$-colouring of the edges of $K$ such that there is an edge of every colour. A locally finite perturbation…

List strengthening conjecture. For every integer $k\geq 2$, if a graph $G$ has minimum degree $\delta(G)\geq k^2$, then $G$ has a $1/k$-majority edge colouring from any lists of si…

Majority edge-colouring conjecture. For every integer $k\geq 2$, if a graph $G$ has minimum degree $\delta\geq k^2$, then $G$ is $1/k$-majority edge $(k+1)$-colourable.

Let $G$ be a Dirac graph on $n$ vertices, meaning a graph with minimum degree at least $n/2$, and let its edge-colouring be proper if every pair of incident edges receives differen…

Let $G$ be a Dirac graph on $n$ vertices, meaning a graph with minimum degree at least $n/2$, and let its edge-colouring be proper if every pair of incident edges receives differen…

Hu, Li and Yang's conjecture. If

Let $K_n$ be the complete graph on $n$ vertices, and let a proper edge-colouring be an edge-colouring in which edges of the same colour do not meet. A rainbow path is a path whose…

Size-version of the Erdős–Hajnal conjecture. There is a positive constant $\epsilon$ such that every colouring $c$ of $K_n$ in colours from $[s]$ avoiding $T$ satisfies

Logarithmic-factor conjecture. For any

Let $K_n$ be the complete graph on $n$ vertices, and let $\chi'(K_n)$ denote its edge-chromatic number. A properly edge-coloured graph is one in which adjacent edges receive distin…

Upper-density conjecture. For every integer $k\geq 3$, every $k$-edge-colouring of $K_{\mathbb{N}}$ contains a monochromatic path $P$ such that

Rainbow bandwidth conjecture. There are $\nu,\beta,z>0$ and $n_0\in\mathbb{N}$ such that, whenever $G$ additionally has an edge-colouring in which every colour appears on at most…

Let $G$ be an edge-coloured multigraph with $n$ colours such that each colour class is a matching of size $n+2$. A rainbow matching is a matching containing at most one edge of eac…

For an integer $r\geq 2$ and a graph $H$, let $f_r(n,H)$ be the smallest number $C$ such that some proper edge-colouring of $K_n$ with $C$ colours contains no $r$ vertex-disjoint c…

Let $G$ be a bridgeless cubic graph. A cycle double cover is a collection of cycles covering every edge exactly twice, and a $2$-factor is a spanning $2$-regular subgraph. Let…