10 problems

Rainbow connection conjecture. A connected graph $G$ has

Let $G$ and $H$ be connected graphs, with $H$ a spanning subgraph of $G$. Chartrand et al.'s conjecture. The strong rainbow connection numbers satisfy … This conjecture is false: t…

Let $G$ be a connected graph, and let $rc(G)$ and $src(G)$ denote its rainbow connection number and strong rainbow connection number, respectively. Let $a$ and $b$ be positive inte…

Strong rainbow connection conjecture. A connected graph $G$ has

Let $G(n,r)$ be a random $r$-regular graph on $n$ vertices, where $r$ is constant and $n\to\infty$. The rainbow connection number $rc(G)$ is the minimum number of colors in an edge…

Li et al.'s conjecture. There exists a constant $C$ such that

Let $G$ be a connected graph with $n$ vertices. Write $\delta(G)$ for its minimum degree and $rc(G)$ for its rainbow connection number, the smallest number of colors in an edge-col…

Krivelevich–Yuster conjecture. If

Let $G$ be a connected graph with $n$ vertices and minimum degree at least $\epsilon n$, where $\epsilon>0$. The rainbow diameter $rd(G)$ is the minimum number of colors in an edge…

Let $G$ be a connected graph, and let $rc(G)$ denote the minimum number of colors in an edge-coloring of $G$ such that every two vertices are joined by a path whose edges have dist…