Xu Qing BA, I Zhong HUANG, Xue Liang LI
An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the graph, there exists a rainbow cut separating u and v. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors required to make G rainbow disconnected. In this paper, we first give some upper bounds for rd(G), and moreover, we completely characterize the graphs which meet the upper bounds of the Nordhaus-Gaddum type result obtained early by us. Secondly, we propose a conjecture that for any connected graph G, either rd(G)=λ+(G) or rd(G)=λ+(G)+1, where λ+(G) is the upper edge-connectivity, and prove that the conjecture holds for many classes of graphs, which supports this conjecture. Moreover, we prove that for an odd integer k, if G is a k-edge-connected k-regular graph, then χ'(G)=k if and only if rd(G)=k. It implies that there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ+(G) for odd k, and also there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ+(G) + 1 for odd k. For k=3, the result gives rise to an interesting result, which is equivalent to the famous Four-Color Problem. Finally, we give the relationship between rd(G) of a graph G and the rainbow vertex-disconnection number rvd(L(G)) of the line graph L(G) of G.
