15 problems

Let $Y$ be a connected bipartite graph on $n\ge 5$ vertices with no non-trivial cut edge and $Y\not=C_n$. The graph $\mathsf{FS}(K_{2,n-2},Y)$ is the friends-and-strangers graph as…

Let $Y$ be a graph on $n\ge 2k\ge 4$ vertices. A $k$-bridge is a set of $k$ edges whose deletion disconnects the graph, and it is non-trivial when neither resulting component is an…

Let $X$ and $Y$ be connected graphs on $n$ vertices. For a graph $G$, write $\delta(G)$ for its minimum degree, and let $\operatorname{FS}(X,Y)$ denote the friends-and-strangers gr…

Disjoint-path connectivity conjecture. The maximum number of disjoint paths between any two permutations $\sigma$ and $\rho$ in $G$ equals $\min\{\deg(\sigma),\deg(\rho)\}$. This w…

Let $X$ be a connected simple graph, and let $c^{(X)}$ and $c^{(\mathsf{Star}_n)}$ be multiplicity lists, with equal total capacity. Let the center of $\mathsf{Star}_n$ have multip…

Let $X,Y\sim\mathcal{G}(n,p)$ denote independent Erdős–Rényi random graphs on $n$ vertices, and let $X,Y\sim\mathcal{G}(K_{n,n},p)$ denote independent random bipartite graphs with…

Let $X$ be an arbitrary connected graph with finite girth, and let $\mathcal C$ be the set of cycle subgraphs in $\mathsf{FS}(X,\operatorname{Star}_n)$ that achieve its girth. For…

Let $Y$ be a graph, let $\overline{Y}$ be its complement, and let $\operatorname{Acyc}(\overline{Y})$ denote the acyclic orientations of $\overline{Y}$. Let…

Let $X$ be a connected graph with finite girth, let $\mathcal C$ be the set of cycle subgraphs of $\mathsf{FS}(X,\textsf{Star}_n)$ that achieve its girth, and for each…

Let $Y$ be a graph on $n\geq 3$ vertices such that its complement is a forest consisting of trees $\mathcal T_1,\dots,\mathcal T_r$ with … If $X$ is a biconnected graph on $n$ vert…

Let $Y$ be a graph on $n$ vertices, and let $\mathsf{FS}(\textsf{Cycle}_n,Y)$ denote its friends-and-strangers graph. The quadratic diameter conjecture asserts that the maximum dia…

Let $d_{r,r}$ denote the parameter defined in the paper’s bipartite minimum-degree theorem, and let $r$ be a positive integer. Bipartite minimum-degree threshold conjecture. We hav…

Let $d_n$ denote the parameter defined in the paper’s minimum-degree theorem for friends-and-strangers graphs. Minimum-degree threshold conjecture. We have … This conjecture predic…

Let $r$ be a positive integer, let $p\in[0,1]$, and let $X$ and $Y$ be independently chosen random graphs from $\mathcal G(K_{r,r},p)$, where $K_{r,r}$ is the complete bipartite gr…

Coprime forest conjecture. If $X$ is biconnected, then $\operatorname{FS}(X,Y)$ is connected.