Geodesic
Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 1023-1036.

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

A total-colored graph G is rainbow total-connected if any two vertices of G are connected by a path whose edges and internal vertices have distinct colors. The rainbow total-connection number, denoted by rtc(G), of a graph G is the minimum number of colors needed to make G rainbow total-connected. In this paper, we prove that rtc(G) can be bounded by a constant 7 if the following three cases are excluded: diam( G ) = 2, diam( G ) = 3, G contains exactly two connected components and one of them is a trivial graph. An example is given to show that this bound is best possible. We also study Erdős-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function f(n, k), where f(n, k) is the minimum value satisfying the following property: if |E(G)| ≥ f(n, k), then rtc(G) ≤ k.
Keywords: Rainbow total-coloring, rainbow total-connection number, complementary graph, Erdős-Gallai type problem 
@article{DMGT_2018_38_4_a10,
     author = {Sun, Yuefang and Jin, Zemin and Tu, Jianhua},
     title = {Rainbow {Total-Coloring} of {Complementary} {Graphs} and {Erd\H{o}s-Gallai} {Type} {Problem} {For} {The} {Rainbow} {Total-Connection} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1023--1036},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a10/}
}
TY  - JOUR
AU  - Sun, Yuefang
AU  - Jin, Zemin
AU  - Tu, Jianhua
TI  - Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 1023
EP  - 1036
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a10/
LA  - en
ID  - DMGT_2018_38_4_a10
ER  - 
%0 Journal Article
%A Sun, Yuefang
%A Jin, Zemin
%A Tu, Jianhua
%T Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 1023-1036
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a10/
%G en
%F DMGT_2018_38_4_a10
Sun, Yuefang; Jin, Zemin; Tu, Jianhua. Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 1023-1036. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a10/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory, GTM 244 (Springer, Berlin, 2008).

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

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

[4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54(2) (2009) 75–81. doi:10.1002/net.20296

[5] L. Chen, B. Huo and Y. Ma, Hardness results for total rainbow connection of graphs, Discuss. Math. Graph Theory 36 (2016) 355–362. doi:10.7151/dmgt.1856

[6] L. Chen, X. Li and Y. Shi, The complexity of determining the rainbow vertex-connection of a graph, Theoret. Comput. Sci. 412 (2011) 4531–4535. doi:10.1016/j.tcs.2011.04.032

[7] X. Huang, H. Li, X. Li and Y. Sun, Oriented diameter and rainbow connection number of a graph, Discrete Math. Theor. Comput. Sci. 16(3) (2014) 51–60.

[8] X. Huang, X. Li, Y. Shi, J. Yue and Y. Zhao, Rainbow connections for outerplanar graphs with diameter 2 and 3, Appl. Math. Comput. 242 (2014) 277–280. doi:10.1016/j.amc.2014.05.066

[9] A. Kemnitz and I. Schiermeyer, Graphs with rainbow connection number two, Discuss. Math. Graph Theory 31 (2011) 313–320. doi:10.7151/dmgt.1547

[10] M. Krivelevich and R. Yuster, The rainbow connection of a graph is ( at most ) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185–191. doi:10.1002/jgt.20418

[11] H. Li, X. Li, Y. Sun and Y. Zhao, Note on minimally d-rainbow connected graphs, Graphs Combin. 30 (2014) 949–955. doi:/10.1007/s00373-013-1309-9

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

[13] X. Li and Y. Sun, Rainbow connection numbers of line graphs, Ars Combin. 100 (2011) 449–463.

[14] X. Li and Y. Sun, Rainbow connection numbers of complementary graphs, Util. Math. 86 (2011) 23–31.

[15] X. Li and Y. Sun, Upper bounds for the rainbow connection numbers of line graphs, Graphs Combin. 28 (2012) 251–263. doi:10.1007/s00373-011-1034-1

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

[17] X. Li and Y. Sun, On the strong rainbow connection of a graph, Bull. Malays. Math. Sci. Soc. 36 (2013) 299–311.

[18] H. Liu, Â. Mestre and T. Sousa, Total rainbow k-connection in graphs, Discrete Appl. Math. 174 (2014) 92–101. doi:10.1016/j.dam.2014.04.012

[19] Y. Ma, Total rainbow connection number and complementary graph, Results Math. 70 (2016) 173–182. doi:10.1007/s00025-015-0469-8

[20] Y. Sun, On two variants of rainbow connection, WSEAS Trans. Math. 12 (2013) 266–276.

[21] Y. Sun, On rainbow total-coloring of a graph, Discrete Appl. Math. 194 (2015) 171–177. doi:10.1016/j.dam.2015.05.012

[22] Y. Sun, On the total rainbow connection of a graph, Acta Math. Appl. Sin. Engl. Ser., accepted.

[23] Y. Sun, Z. Jin and F. Li, On total rainbow k-connected graphs, Appl. Math. Comput. 311 (2017) 223–227. doi:10.1016/j.amc.2017.05.020

[24] K. Uchizawa, T. Aoki, T. Ito, A. Suzuki and X. Zhou, On the rainbow connectivity of graphs: complexity and FPT algorithms, Algorithmica 67 (2013) 161–179. doi:10.1007/s00453-012-9689-4