Geodesic
More on the Rainbow Disconnection in Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1185-1204.

Voir la notice de l'article provenant de la source Library of Science

Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. In this paper, we first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ k ≤ n − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(G) = 3 for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.
Keywords: edge-coloring, edge-connectivity, rainbow disconnection coloring (number), Erdős-Gallai type problem, Nordhaus-Gaddum type bounds, complexity, NP-hard (complete) 
@article{DMGT_2022_42_4_a10,
     author = {Bai, Xuqing and Chang, Renying and Huang, Zhong and Li, Xueliang},
     title = {More on the {Rainbow} {Disconnection} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1185--1204},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a10/}
}
TY  - JOUR
AU  - Bai, Xuqing
AU  - Chang, Renying
AU  - Huang, Zhong
AU  - Li, Xueliang
TI  - More on the Rainbow Disconnection in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1185
EP  - 1204
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a10/
LA  - en
ID  - DMGT_2022_42_4_a10
ER  - 
%0 Journal Article
%A Bai, Xuqing
%A Chang, Renying
%A Huang, Zhong
%A Li, Xueliang
%T More on the Rainbow Disconnection in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1185-1204
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a10/
%G en
%F DMGT_2022_42_4_a10
Bai, Xuqing; Chang, Renying; Huang, Zhong; Li, Xueliang. More on the Rainbow Disconnection in Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1185-1204. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a10/

[1] S. Akbari, D. Cariolaro, M. Chavooshi, M. Ghanbari and S. Zare, Some criteria for a graph to be Class 1, Discrete Math. 312 (2012) 2593–2598. https://doi.org/10.1016/j.disc.2011.09.035

[2] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466–546. https://doi.org/10.1016/j.dam.2011.12.018

[3] T. Beşeri, Edge Coloring of a Graph (İzmir Institute of Technology, İzmir, Turkey, 2004).

[4] J.A. Bondy and U.S.R. Murty, Graph Theory (Grad. Texts in Math. 244 Springer-Verlag, London, 2008).

[5] S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connectivity, J. Comb. Optim. 21 (2011) 330–347. https://doi.org/10.1007/s10878-009-9250-9

[6] G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021. https://doi.org/10.7151/dmgt.2061

[7] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85–98.

[8] L. Chen, X. Li and H. Lian, Nordhaus-Gaddum type theorem for rainbow connection number of graphs, Graphs Combin. 29 (2013) 1235–1247. https://doi.org/10.1007/s00373-012-1183-x

[9] A.G. Chetwynd and A.J.W. Hilton, Regular graphs of high degree are 1 -factorizable, Proc. Lond. Math. Soc. (3) 50 (1985) 193–206. https://doi.org/10.1112/plms/s3-50.2.193

[10] G.A. Dirac, A property of 4 -chromatic graphs and remarks on critical graphs, J. Lond. Math. Soc. 27 (1952) 85–92. https://doi.org/10.1112/jlms/s1-27.1.85

[11] G.A. Dirac, Circuits in critical graphs, Monatsh. Math. 59 (1955) 178–187. https://doi.org/10.1007/BF01303792

[12] P. Elias, A. Feinstein and C.E. Shannon, A note on the maximum flow through a network, IEE Trans. Inform. Theory, IT 2 (1956) 117–119. https://doi.org/10.1109/TIT.1956.1056816

[13] L.R. Ford Jr. and D.R. Fulkerson, Maximal flow through a network, Canad. J. Math. 8 (1956) 399–404. https://doi.org/10.4153/CJM-1956-045-5

[14] F. Harary and T.W. Haynes, Nordhaus-Gaddum inequalities for domination in graphs, Discrete Math. 155 (1996) 99–105. https://doi.org/10.1016/0012-365X(94)00373-Q

[15] A. Hellwig and L. Volkmann, The connectivity of a graph and its complement, Discrete Appl. Math. 156 (2008) 3325–3328. https://doi.org/10.1016/j.dam.2008.05.012

[16] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718–720. https://doi.org/10.1137/0210055

[17] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1–38. https://doi.org/10.1007/s00373-012-1243-2

[18] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs Math. Springer, New York, 2012). https://doi.org/10.1007/978-1-4614-3119-0

[19] X. Li and Y. Sun, An updated survey on rainbow connections of graphs—a dynamic survey, Theory Appl. Graphs 0 (2017) Art. 3. https://doi.org/10.20429/tag.2017.000103

[20] W. Mader, Ein Extremalproblem des Zusammenhangs von Graphen, Math. Z. 131 (1973) 223–231. https://doi.org/10.1007/BF01187240

[21] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177. https://doi.org/10.2307/2306658

[22] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25–30, in Russian.