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$.
Xu-Qing Bai, Bi Li, Chuan-Dong Xu, Xin Zhang
. Fast Algorithm for the rainbow disconnection Coloring of 2-Trees[J]. Journal of the Operations Research Society of China, 2026
, 14(1)
: 149
-161
.
DOI: 10.1007/s40305-023-00498-w
[1] Bondy, J.A., Murty, U.S.R.: Graph theory. In: Graduate Texts in Mathematics, vol. 244. Springer, Berlin (2008)
[2] Goedeking, P.: Networks in Aviation: Strategies and Structures. Springer Science & Business Media, London (2010)
[3] Peterson, L.L., Davie, B.S.: Computer Networks: a Systems Approach. Elsevier, Amsterdam (2007)
[4] Bell, M.G., Iida, Y.: Transportation Network Analysis. Wiley, New York (1997)
[5] Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133, 85-98(2008)
[6] Li, X., Shi, Y., Sun, Y.: Rainbow connections of graphs: a survey. Graphs Combin. 29, 1-38(2013)
[7] Li, X., Sun, Y.: An updated survey on rainbow connections of graphs—a dynamic survey. Theory Appl. Graphs 0, 1-67(2017)
[8] Li, X., Sun, Y.: Rainbow Connections of Graphs. Springer, New York (2012)
[9] Chartrand, G., Devereaux, S., Haynes, T.W., Hedetniemi, S.T., Zhang, P.: rainbow disconnection in graphs. Discuss. Math. Graph Theory 38, 1007-1021(2018)
[10] Bai, X., Li, X.: Graph colorings under global structural conditions. arXiv:2008.07163(2020)
[11] Bollobás, B.: On graphs with at most three independent paths connecting any two vertices. Studia Sci. Math. Hungar. 1, 137-140(1966)
[12] Bollobás, B.: Extremal Graph Theory. Academic Press Inc, London (1978)
[13] Elias, P., Feinstein, A., Shannon, C.E.: A note on the maximum flow through a network. IRE Trans. Inform. Theory IT 2, 117-119(1956)
[14] Ford, L.R., Jr., Fulkerson, D.R.: Maximal flow through a network. Canad. J. Math. 8, 399-404(1956)
[15] Bai, X., Chang, R., Huang, Z., Li, X.: More on rainbow disconnection in graphs. Discuss. Math. Graph Theory. 42, 1185-1204(2022)
[16] Bai, X., Huang, Z., Li, X.: Bounds for the rainbow disconnection number of graphs. Acta Math. Sin. Engl. Ser. 38, 384-396(2022)
[17] Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combin. Theory Ser. B 16, 47-56(1974)
[18] Heggernes, P.: Treewidth, partial k-trees, and chordal graphs. In: Partial Curriculum in INF334 Advanced Algorithmical Techniques. Department of Informatics, University of Bergen, Norway (2005)
[19] Wald, J.A., Colbourn, C.J.: Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13(2), 159-167(1983)
