85 problems

Let $r\in\mathbb{N}$, and let the edges of a complete graph be coloured with $r$ colours. A monochromatic cycle partition is a partition of the vertex set into vertex sets, each in…

Bollobás–Erdős conjecture. If

Let $K_n$ be the complete graph on $n$ vertices, with $n\geqslant5$, and suppose its edges are properly edge-coloured. A Hamilton path is a spanning path, and it is rainbow when al…

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…

Let $G$ be a bridgeless cubic graph. A collection of six perfect matchings of $G$ may contain repetitions, and each edge of $G$ is counted according to its membership in the collec…

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…

Let $K_n$ be the complete graph on $n$ vertices, and let a proper edge-colouring be an edge-colouring in which adjacent edges receive different colours. A rainbow spanning tree is…

Norine's conjecture. Every antipodal $2$-edge-colouring of $Q_n$ contains a monochromatic path from some vertex to its antipode.

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…

Exponential lower-bound conjecture. One has

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 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…

Let $r\geq 3$ be an integer, and let $G$ be a graph without isolated edges and with maximum degree $\Delta$. Its $r$-distant sum distinguishing index $\chi'\_{\Sigma,r}(G)$ is the…

Let $K_{n,n}$ be a balanced complete bipartite graph whose edges are coloured with $r$ colours. A vertex-partition into monochromatic paths is a partition of all vertices into path…

Odd-colour phase-transition conjecture. One has

Bollobás–Gyárfás jump conjecture. The function satisfies

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…

A red/blue edge-colouring of a $3$-graph is called colour balanced on a perfect matching when the matching contains the same number of red and blue edges. Let the two thresholds be…

Norine's and related conjectures. For every $n$, the following assertions hold:

Multicolour enabling graph conjecture. The upper bound in the paper's multicolour theorem is correct when $k$ is sufficiently large in terms of $r$; equivalently, for sufficiently…

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…