42 problems

Let $P_k$ be the path on $k$ vertices, let $K_s$ be the complete graph on $s$ vertices, and let $sat(n,H)$ denote the minimum number of edges in an $H$-saturated graph on $n$ verti…

Let $C_k$ denote the cycle graph on $k$ vertices, and let $\mathrm{sat}(n,C_k)$ be its saturation number. Füredi–Kim conjecture. There exists a constant $k_0$ such that … holds for…

Let $K_{n,n}$ and $K_{s,t}$ be complete bipartite graphs, with $s$ and $t$ fixed. Moshkovitz–Shapira conjecture. For sufficiently large $n$, … This conjecture concerns the asymptot…

Erdős–Tuza conjecture. The minimum satisfies

Let $r$ be the number of parts, and let $K_{2,\ldots,2}$ be the complete multipartite graph with $r$ parts, each of size $2$. For a graph $H$, write $sat(n,H)$ for the minimum numb…

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…

Let $F'$ be a graph. An extremal graph for $K_1\vee F'$ is a graph attaining the saturation number, and a vertex has full degree if it is adjacent to every other vertex. Full-degre…

Let $F'$ be the graph obtained from a graph $F$ by deleting all isolated vertices, and let … For fixed $F'$, consider extremal graphs for $K_1\vee(F'\cup \ell K_1)$. Connectivity c…

Let $F$ be a graph, and consider the saturation number $\mathrm{sat}(n,K_1\vee F)$. Cameron and Puleo's inequality gives the equality … for some choices of $F$ but not others. Deco…

Let $tP_4$ denote the disjoint union of $t$ copies of the path on four vertices. For a graph $F$, write $sat(n,F)$ for the minimum number of edges in an $F$-saturated graph on $n$…

Packing–saturation conjecture.

Separation conjecture. For any $r=r(k)\geq 3$,

Wheel saturation recurrence. For every integer $k\geq 4$, there exists a constant $N_k$ such that, for all $n>N_k$,

Let $G$ be a planar graph with minimum degree at least $3$, and let $e(G)$ denote its number of edges. Write $\operatorname{sat}_{\mathcal{P}}(G)$ for the minimum number of edges i…

Let $\delta\geq2$ be fixed, and let $w\in\mathbb Q\cap[\delta/2,\delta-1]$. Density-realization conjecture. There exists a graph $F$ such that … This would extend the dense-range r…

Let $F$ be a graph, and let $w_F$ denote its weak saturation limit. Rationality conjecture. For any graph $F$, $w_F$ is rational. This asks whether all weak saturation limits are r…

For a maximal planar graph $G$ on $n$ vertices, let its plane-saturation ratio be the relevant ratio measuring the size of a largest plane-saturated subgraph relative to $G$. Plane…

Let $K_k^n$ be the complete $k$-partite graph with $n$ vertices in each part, let $C_{\geq\ell}$ be the family of cycles of length at least $\ell$, and let $\Omega^{(\ell,k,n)}$ be…

Let $K_4^n$ be the complete $4$-partite graph with $n$ vertices in each part, and let $C_4$ be the cycle of length four. Complete four-partite $C_4$-saturation conjecture. For ever…

Let $K_{n_1,n_2}$ be a complete bipartite graph, and let $C_{2\ell}$ denote the cycle of length $2\ell$. Even-cycle bipartite saturation conjecture. For $\ell\geq 4$ and…

Fix $k\geq 2$, let $K_k^n$ be the complete $k$-partite graph with $n$ vertices in each part, and let $F$ be a subgraph of $K_k^n$. Partite saturation limit conjecture. The limit ……

Let $G$ be an edge-ordered graph, and let $sat_e(n,G)$ denote its edge-ordered saturation function. Almost-linear saturation conjecture. For every edge-ordered graph $G$, … This is…

Let $G$ be an edge-ordered graph, and let $sat_e(n,G)$ denote its edge-ordered saturation function. Near-linear saturation conjecture. For every edge-ordered graph $G$, … The paper…

Disjoint-neighborhood saturation conjecture. Under these hypotheses,

Let $G$) be an edge-ordered graph and let $e_0$ be an isolated minimal edge of $G$. Write $F=e_0+G$. The isolated-edge saturation conjecture. … The authors present this as a candid…