Abstract: Given a connected graph $G=(V, E)$, a rainbow disconnection $k$-coloring of $G$ is a $k$-edge coloring of $G$ such that for each pair of vertices $u, v \in V$, there is a rainbow (edge) cut of $u, v$, which is a subset $\mathrm{RC}(u, v) \subseteq E$ such that $u, v$ are disconnected in $G \backslash \mathrm{RC}(u, v)$ and that all edges in $\mathrm{RC}(u, v)$ have different colors. The minimum integer $k$ such that $G$ admits a rainbow disconnection $k$-coloring is the rainbow disconnection number of $G$, denoted by $\operatorname{rd}(G)$. It has been shown that $\operatorname{rd}(G)$ is closely related to the maximum number $\lambda^{+}(G)$ of edge disjoint paths among all pairs of vertices in $G$. In this paper, we propose a polynomial-time algorithm for finding a rainbow disconnection $\operatorname{rd}(G)$-coloring of a 2-tree, a graph $G$ formed by starting with a triangle and then repeatedly adding vertices in such a way that each added vertex is adjacent to two ends of an edge. Moreover, the algorithm shows that $\operatorname{rd}(G)=\lambda^{+}(G)$ if $G$ is a 2-tree. This justifies a conjecture of Bai et al. [MR4385957] in 2-trees, which states that $\operatorname{rd}(G)$ is either $\lambda^{+}(G)$ or $\lambda^{+}(G)+1$ for each graph $G$.

Key words: rainbow disconnection coloring, 2-Tree, Dynamic programming, Polynomial-time algorithm