53 problems

Let $K_n$ be the complete graph on $n$ vertices with its edges colored using three colors. Let $F(G)$ be the number of rainbow triangles in a coloring $G$, and let … A coloring is…

Let $r$ and $t$ be positive integers, and let $r(t)$ denote the two-color Ramsey number: the least integer $m$ such that every $2$-coloring of the edges of the complete graph on…

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…

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$,

Wu–Magnant–Nowbandegani–Xia conjecture.

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.

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…

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…

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…

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…

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

For a digraph $D$, define the balanced degree of a vertex $x$ by … A digraph is strongly locally irregular if $\sigma(x)\neq\sigma(y)$ for every arc $xy$, and let…

For a digraph $D$, two adjacent vertices are weakly distinguished when their outdegree–indegree pairs differ. Let $\mathrm{lir}(D)$ be the minimum number of colors in an arc colori…

A sink-source path is an oriented path containing an arc directed into a vertex and an arc directed out of that vertex, as used in the source. For $a,b\in\{+,-\}$, define $(a,b)$-l…

For $a,b\in\{+,-\}$, a digraph is $(a,b)$-locally irregular if, for every arc $uv$, $d^a(u)\neq d^b(v)$; let $\mathrm{lir}^{(+,+)}(D)$ be the minimum number of colors in an arc col…

Let $G$ be a connected locally irregular colorable graph, let $B$ be the bow-tie graph, and let $\mathrm{lir}(G)$ denote the minimum number of locally irregular subgraphs whose edg…

Keevash–Mubayi–Sudakov–Verstraëte conjecture. There is a constant $C$ such that every properly edge-colored $n$-vertex graph with at least $Cn\log n$ edges contains a rainbow cycle…

Let $\rho(3,6,\delta)$ denote the asymptotic maximum edge density of an $n$-vertex graph with independence number at most $\delta n$ admitting a 2-edge-coloring with no monochromat…

Norine's conjecture. For $n\ge 2$, any antipodal edge-coloring of $Q_n$ contains antipodal vertices $u$ and $\bar u$ such that $u$ and $\bar u$ are joined by a monochromatic path.

Let $G$ be a connected graph that is not a Shannon triangle of type $(2,2,2)$ or type $(2,2,1)$. Write $\chi_{\text{odd}}'(G)$ for the odd chromatic index, and call an edge special…

No-lonely-color conjecture. There is a function $f$ such that, whenever no color is lonely on any cycle of $G$, one has