28 problems

Let $G$ be a nonabelian finite simple group, and let $\operatorname{diam}(G)$ denote the maximum of $\operatorname{diam}(G,X)$ over all generating sets $X$ of $G$. Babai’s conjectu…

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 a graph of diameter $3$ with $n$ vertices, and let $Omega_\omega(G)$ denote the $omega$-cover pebbling parameter used in the paper. For $omega\geq 1$, diameter-three…

Consider the two diameter conjectures stated for transitive permutation groups and nonabelian finite simple groups, whose bounds have the forms $\operatorname{diam}(G)\ll n^{O(1)}$…

Let $G\leq S_n$ be a transitive permutation group. The diameter of $G$ is defined using the maximum over generating sets, namely…

Let $s\geq 3$ and let $\mathcal{D}_{s,n}$ be the $(1:b)$ Maker–Breaker game on the edges of $K_n$ in which Maker wins precisely when her spanning subgraph has diameter at most $s$.…

Conjecture on $m(n,d)$.

Koh–Tay conjecture. The graph $G$ has an orientation of diameter two. This conjecture was proved by Cochran, Czabarka, Dankelmann and Székely in 2021, so it is no longer open.

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 finite, simple graph, and let $D_2(G)=G_2$ be its $2$-distance graph: it has the same vertex set as $G$, with two vertices adjacent exactly when their geodesic distanc…

Let $K_n$ be the complete graph, let $\mathsf{WST}$ be the weighted spanning tree model on an electric network with the random edge weights described in the surrounding text, and l…

Let $K_n$ be the complete graph on $n$ vertices, let $\beta_n=n^{\alpha}$ with $\alpha\in\left(1,\frac{4}{3}\right)$, and let $\mathsf{WST}_n^{\beta_n}$ denote the weighted spannin…

Let $G$ be a graph, let $\tau(G)$ denote the minimum number of monochromatic subgraphs in a covering set for $G$, and let $u(G)$ denote the maximum size of an independent set, wri…

Let $G$ be a bridgeless graph of order $n$ and minimum degree $\delta\geq 2$, and let $\overrightarrow{\operatorname{diam}}(G)$ denote the minimum diameter over all strongly connec…

Colorful Bárány–Katchalski–Pach conjecture. Under these hypotheses, there is an index $k\in[2d]$ whose entire family has intersection of diameter at least $c d^{-1/2}$, for some ab…

Bárány–Katchalski–Pach conjecture. Under these hypotheses, the intersection of the entire family has diameter at least $c d^{-1/2}$.

Gliviak–Knor–Šoltés conjecture. The minimum order of a non-self-centered radially maximal graph of radius $r$ is

Dutton–Medidi–Brigham converse conjecture. There exists a radially maximal graph with radius $r$ and diameter $d$.

Disk sharpness conjecture. The estimate

Bollobás's conjecture. $(d,k)$-graphs of size $n\geq (1-\varepsilon)d^k$ always exist for sufficiently large $d$ and $k$.

Andova–Skrekovski conjecture. If $G$ is any fullerene graph on $n$ vertices, then

Let $\{P_i:i\in I\}$ be a family of closed convex sets in $\mathbb{R}^n$ such that … The authors ask whether there exist $s\leqslant 2n$ and $i_1,\ldots,i_s\in I$ such that … where…

Non-existence conjecture. There is no bipartite $(d,3,-4)$-graph with $d\ge 6$.

Diameter-three oriented-diameter conjecture. Every bridgeless graph with diameter at most $3$ has oriented diameter at most $9$.