Abstract. For each [Formula: see text], we construct a finite set [Formula: see text] of multigraphs such that for each graph [Formula: see text] of girth at least 5 obtained from a multigraph [Formula: see text] by subdividing each edge at least two times, [Formula: see text] has twin-width at most [Formula: see text] if and only if [Formula: see text] has no minor in [Formula: see text]. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs [Formula: see text] such that each long subdivision of [Formula: see text] has twin-width 4. As a corollary, we show that the [Formula: see text] grid has twin-width 4, which answers a question of Schidler and Szeider.

Abstract. We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph [Formula: see text] is called [Formula: see text]- rainbow saturated if [Formula: see text] does not contain a rainbow copy of [Formula: see text] and adding an edge of any color to [Formula: see text] creates a rainbow copy of [Formula: see text]. The rainbow saturation number [Formula: see text] is the minimum number of edges in an [Formula: see text]-vertex [Formula: see text]-rainbow saturated graph. Girão, Lewis, and Popielarz conjectured that [Formula: see text] for fixed [Formula: see text]. Disproving this conjecture, we establish that for every [Formula: see text], there exists a constant [Formula: see text] such that [Formula: see text] and [Formula: see text]. Recently, Behague, Johnston, Letzter, Morrison, and Ogden independently gave a slightly weaker upper bound which was sufficient to disprove the conjecture. They also introduced the weak rainbow saturation number and asked whether this is equal to the rainbow saturation number of [Formula: see text], since the standard weak saturation number of complete graphs equals the standard saturation number. Surprisingly, our lower bound separates the rainbow saturation number from the weak rainbow saturation number, answering this question in the negative. The existence of the constant [Formula: see text] resolves another of their questions in the affirmative for complete graphs. Furthermore, we show that the conjecture of Girão, Lewis, and Popielarz is true if we have an additional assumption that the edge-colored [Formula: see text]-rainbow saturated graph must be rainbow. As an ingredient of the proof, we study graphs which are [Formula: see text]-saturated with respect to the operation of deleting one edge and adding two edges.

Bonnet et al. [ J. ACM, 69 (2022), 3] introduced the twin-width of a graph. We show that the twin-width of an $n$-vertex graph is less than $(n+\sqrt{n\ln n}+\sqrt{n}+2\ln n)/2$, and the twin-width of an $m$-edge graph for a positive $m$ is less than $\sqrt{3m}+ m^{1/4} \sqrt{\ln m} / (4\cdot 3^{1/4}) + 3m^{1/4} / 2$. Conference graphs of order $n$ (when such graphs exist) have twin-width at least $(n-1)/2$, and we show that Paley graphs achieve this lower bound. We also show that the twin-width of the Erdös--Rényi random graph $G(n,p)$ with $1/n\leq p\leq 1/2$ is larger than $2p(1-p)n - (2\sqrt{2}+\varepsilon)\sqrt{p(1-p)n\ln n}$ asymptotically almost surely for any positive $\varepsilon$. Last, we calculate the twin-width of random graphs $G(n,p)$ with $p\leq c/n$ for a constant $c<1$, determining the thresholds at which the twin-width jumps from $0$ to $1$ and from $1$ to $2$.

By considering graphs as discrete analogues of Riemann surfaces, Baker and Norine [ Adv. Math., 215 (2007), pp. 766--788] developed a concept of linear systems of divisors for graphs. Building on this idea, a concept of gonality for graphs has been defined and has generated much recent interest. We show that there are connected graphs of treewidth 2 of arbitrarily high gonality. We also show that there exist pairs of connected graphs $\{G,H\}$ such that $H\subseteq G$ and $H$ has strictly lower gonality than $G$. These results resolve three open problems posed in a recent survey by Norine [in Surveys in Combinatorics, London Math. Soc. Lecture Note Ser. 424, Cambridge University Press, Cambridge, 2015, pp. 221--260].