13 problems

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…

Frieze–Krivelevich conjecture. There exists a constant $\alpha>0$ such that every globally $\alpha n$-bounded coloring contains any spanning tree with bounded maximum degree.

Let $k,t,n$ be positive integers, let $G=kP_4\cup tP_2$, and let $S\subseteq E(G)$ consist of internal edges of the $P_4$ components. A set of edges is neutral for the anti-Ramsey…

Rainbow anti-Ramsey conjecture. The rainbow anti-Ramsey number for $(t+2)$ vertex-disjoint triangles satisfies

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…

Let $G$ be an edge-colored graph on $n$ vertices, let $e(G)$ denote its number of edges, and let $c(G)$ denote its number of colors. A proper $mK_3$ is a collection of $m$ vertex-d…

Let $S(N)$ be the set of natural numbers $q$ such that $4\leq q\leq N$ and, for every $n_0$, there is some $n\geq n_0$ with $n\equiv 1\pmod{\ell}$ and a balanced coloring of $K_n$…

Chromatic-discrepancy conjecture. The chromatic discrepancy of $G$ is at least $\chi-\omega$.

Extremal characterization conjecture. If $D$ contains no rainbow triangles and

Constant-error rainbow tree conjecture. There is a constant $C$ such that every properly coloured $K_n$ has a rainbow copy of every tree on $n-C$ vertices.

Let $P_n$ and $C_n$ denote, respectively, the path and cycle on $n$ vertices, and let $\rho_R(G)$ denote the replication number of a graph $G$. The cycle–path replication conjectur…

Let $P_n$ be the path on $n$ vertices, and let $\rho_R(P_n)$ denote its replication number. The notation $O(n)$ means a quantity bounded in absolute value by a constant multiple of…

Let $P_n$ be the path on $n$ vertices, and let $\rho_R(P_n)$ denote its replication number. For odd $n\geq 1$, write the upper-bound formula according to the residue class of $n$ m…