81 problems

Let $G$ be an $n$-vertex graph whose edges are colored with $n$ colors, and let the rainbow girth be the minimum length of a rainbow cycle, with value $infty$ if no rainbow cycle e…

Gyárfás–Lehel conjecture. In every $r$-coloring of the edges of $G$, the vertex set can be covered by the vertices of at most $2r-2$ monochromatic components.

Milićević's conjecture. For every $r$, there is a constant $D(r)$ such that every $r$-edge-coloured complete graph can be covered by $r-1$ monochromatic components of diameter at m…

Bollobás's conjecture. For any $\varepsilon>0$, there is an integer $N(\varepsilon,t)$ such that every such $2$-coloring of $K_n$ with $n\geq N(\varepsilon,t)$ contains a copy of o…

Let $K_m^h$ and $K_n^h$ be complete $h$-uniform hypergraphs on $m$ and $n$ vertices, respectively, where $n>m$. A 1-factorization is an edge-coloring whose color classes are $1$-re…

Let $r\geq 3$, $k\geq h$, and let $H$ be an $r$-color-critical graph with $h$ edges. For sufficiently large $n$, an $n$-vertex $k$-color extremal multigraph of $H$ is either formed…

Let $H$ be a graph, and let $f(n,H)$ denote the maximum number of edges not contained in any monochromatic copy of $H$ in a $2$-edge-coloring of the complete graph $K_n$. Keevash–S…

Let $K_k$ be the complete graph on $k$ vertices, let $\mathcal{R}(K_k)$ be the family of rainbow edge-colorings of $K_k$, and let $\operatorname{sat}_t(n,\mathcal{R}(K_k))$ denote…

Let $G$ be a graph with an edge coloring $\phi$, let $r(G,\phi)$ be the size of a largest rainbow matching in $G$, and let $\hat{\delta}(G,\phi)$ be the minimum color degree of $G$…

Let $S$ be a spectrum of rainbow cycle lengths, namely the set of cycle lengths occurring as rainbow cycles under a fixed edge-coloring. Spectrum regularity conjecture. The asympto…

Let $G\sim G(n,p)$ be an Erdős–Rényi random graph, where $p\gg 1/n$ and $p=o(1)$, and let $m_r(G)$ denote the minimum possible order of the largest monochromatic connected componen…

Nonadjacent maximum-degree measurable edge-coloring conjecture. For every probability measure $\mu$ on $V$,

Unbalanced bipartite measurable edge-coloring conjecture. For every probability measure $\mu$ on $V$,

Finite-degree Borel Shannon edge-coloring conjecture. If $\mathsf{asi}(G)<\infty$, then

Wu–Magnant–Nowbandegani–Xia conjecture.

Gyárfás–Kiraly conjecture. For all $t\geq 1$ and $r\geq 3$,

For integers $r$ and $s\geq r-1$, let $G_1,\ldots,G_s\subseteq\binom{[n]}{2}$ be graphs whose edges are $(r-1)$-star edge-colored and whose underlying graphs are $K_r$-free. Here…

A normal edge-coloring of a cubic multigraph is a proper edge-coloring in which every edge is adjacent to edges colored with either four distinct colors or two distinct colors. The…

Schrijver's conjecture. If $G$ is a properly edge-colored $d$-regular graph, then $G$ contains a rainbow path of length $d-1$.

DeBiasio–Kamel–McCourt–Sheats conjecture. There exists a constant $d=d(\alpha)$, depending only on $\alpha$, such that every $r$-colouring of $G$ has $(r-1)\alpha$ monochromatic co…

English–McCourt–Mattes–Phillips conjecture. In every $2$-coloring of the edges of $G^c$, there exist $A,B\subseteq V$ and colors $i,j\in[2]$ such that

Let $G$ be a graph with independence number $\alpha(G)=\alpha$, and consider an $r$-edge coloring of $G$. A monochromatic connected component has bounded diameter if the distances…

Let $G$ be a graph on $2n$ vertices that is the union of three disjoint perfect matchings. An $(a_1,a_2,a_3)$-matching is a matching containing exactly $a_i$ edges from the $i$th p…

Let $G$ be a complete bipartite graph on $2n$ vertices whose edge set is decomposed into perfect matchings $M_i$, for $i=1,\ldots,n$. Let $a_1,\ldots,a_n\in\mathbb{N}_0$ be nonnega…

Let $\rho_{r,k}(n)$ denote the maximum number of edge colorings of an $n$-vertex graph with $r$ colors that contain no rainbow copy of $K_k$. Let $T_{k-1}(n)$ be the Turán graph, t…